【dfs】hdu 1175 连连看题目链接：hdu 1175 连连看题目大意
连连看，问能否成功？
题意很简单，就是我们平时玩的连连看的游戏规则，貌似dfs和bfs都能做，笔者就做了个dfs(好想)，超时了好几次，原因是dfs(int d)与终点的d重载矛盾了，所以还是要小心。
说一下思路
【In addition】搜索的关键在于剪枝！优化！
参考代码;const int _max = 1e3 + 10;int n,m,a,b,c,d;int G[_max][_max],dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};bool ok,vis[_max][_max];void dfs(int x,int y,int p,int t){//横坐标x,纵坐标y，上一步方向p,转折次数t if(x>n||y>m||x<1||y<1||t>2||ok) return; if(x==c&&y==d&&t<=2){ok=true;return;} if(t==2&&x!=c&&y!=d) return;//完美的剪枝，，如果转了2次，但是目标与当前位置不在同一行或同一列 vis[x][y]=1; for(int i = 0;i < 4&&!ok; ++ i) {//i=0,1,2,3表示下、上、右、左四个方向int _x=x+dir[i][0];int _y=y+dir[i][1];if(_x==c&&_y==d);else if(G[_x][_y]||vis[_x][_y]) continue; // vis[_x][_y]=1;if(i==p||p==-1) dfs(_x,_y,i,t);else dfs(_x,_y,i,t+1);vis[_x][_y]=0; }}int main(){// freopen(“input.txt”,”r”,stdin); while(scanf(“%d%d”,&n,&m)==2&&n||m){for(int i = 1 ;i <= n; ++ i)for(int j = 1;j <= m; ++ j )scanf(“%d”,&G[i][j]);int T;scanf(“%d”,&T);while(T–){scanf(“%d%d%d%d”,&a,&b,&c,&d);if(G[a][b]!=G[c][d]||!G[a][b]) {puts(“NO”);continue;}//剪枝做个优化clr(vis,0);ok=false;dfs(a,b,-1,0);//0,1,2,3均表示一种方向，初始方向取-1最好puts(ok?”YES”:”NO”);} } return 0;}
无论才能知识多么卓着，如果缺乏热情，则无异纸上画饼充饥，无补于事。
