题目链接：连连看
题意：
给出一张n*m的图，有q次询问，每次询问给出两个位置，问这两个位置是否能够相消
相消的条件：
1.两个位置可以用线相连且弯折度不超过2
2.两位置数字相同且不为0
分析：
用一个二维数组存储该位置的弯折度，注意剪枝顺序，详情见代码
一开始写dx[],dy[]的时候写成一维，却wa，不清楚为什么
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 6 int n,m,a[1010][1010],dx[5]={0,0,-1,0,1},dy[5]={0,1,0,-1,0},q,x1,y1,x2,y2,cnt,fang[1010][1010],flag; 7 8 void dfs(int x,int y,int cnt,int f) 9 { 10 //注意剪枝的顺序 11 if(flag) return ;//若已有结果，则直接返回 12 if(x<1||y<1||x>n||y>m||cnt>2) return ; 13 if((x==x2)&&(y==y2)) {flag=1;return ;} 14 if(a[x][y]) return ; 15 //若该点已有弯折度且当前局面到x,y的弯折度大于其他局面的弯折度，则返回 16 if((fang[x][y]!=-1)&&(cnt>=fang[x][y])) return ; 17 fang[x][y]=cnt; 18 for(int i=1;i<=4;++i) 19 { 20 int xx=x+dx[i],yy=y+dy[i]; 21 if(f!=i) dfs(xx,yy,cnt+1,i);else dfs(xx,yy,cnt,i); 22 } 23 } 24 25 int main() 26 { 27 while(scanf("%d%d",&n,&m)!=EOF) 28 { 29 if(n==0&&m==0) return 0; 30 for(int i=1;i<=n;++i)for(int j=1;j<=m;++j) {scanf("%d",&a[i][j]);} 31 for(scanf("%d",&q);q--;) 32 { 33 memset(fang,-1,sizeof(fang)); 34 scanf("%d%d%d%d",&x1,&y1,&x2,&y2); 35 flag=0; 36 if(a[x1][y1]!=a[x2][y2]||a[x1][y1]==0) {puts("NO");continue;} 37 fang[x1][y1]=0; 38 for(int i=1;i<=4;++i) dfs(x1+dx[i],y1+dy[i],0,i); 39 if(flag) puts("YES");else puts("NO"); 40 } 41 } 42 }