3 4 1 2 3 4 0 0 0 0 4 3 2 1 4 1 1 3 4 1 1 2 4 1 1 3 3 2 1 2 4 3 4 0 1 4 3 0 2 4 1 0 0 0 0 2 1 1 2 4 1 3 2 3 0 0Sample Output
YES NO NO NO NO YES
直接暴力深搜能过，和一般迷宫题先比多记录个方向和转折点而已。
向上向下向左向右
#include<stdio.h> #include<algorithm> #include<iostream> #include<string.h> using namespace std; int n,m; int flag=0; int a[1100][1100]; int vis[1100][1100]={0}; //t 1234 void dfs(int x1,int y1,int x2,int y2,int t,int f,int vis[1100][1100]) { int h1,h2; if(f>2) return; if(abs(x1-x2)+abs(y1-y2)<=1) { if(f<=1) flag=1; else if((t==1&&x1-x2==1)||(t==2&&x2-x1==1) ||(t==3&&y1-y2==1)||(t==4&&y2-y1==1)) flag=1; } if(flag) return; //ср if(y1+1<=m&&a[x1][y1+1]==0&&vis[x1][y1+1]==0) { h1=f; h2=t; vis[x1][y1+1]=1; if(t!=4&&t!=0) h1=f+1; h2=4; dfs(x1,y1+1,x2,y2,h2,h1,vis); vis[x1][y1+1]=0; } if(x1+1<=n&&a[x1+1][y1]==0&&vis[x1+1][y1]==0) { h1=f; h2=t; vis[x1+1][y1]=1; if(t!=2&&t!=0) h1=f+1; h2=2; dfs(x1+1,y1,x2,y2,h2,h1,vis); vis[x1+1][y1]=0; } if(y1-1>0&&a[x1][y1-1]==0&&vis[x1][y1-1]==0) { h1=f; h2=t; vis[x1][y1-1]=1; if(t!=3&&t!=0) h1=f+1; h2=3; dfs(x1,y1-1,x2,y2,h2,h1,vis); vis[x1][y1-1]=0; } if(x1-1>0&&a[x1-1][y1]==0&&vis[x1-1][y1]==0) { h1=f; h2=t; vis[x1-1][y1]=1; if(t!=1&&t!=0) h1=f+1; h2=1; dfs(x1-1,y1,x2,y2,h2,h1,vis); vis[x1-1][y1]=0; } } int main() { while(1) { memset(a,0,sizeof(a)); scanf("%d%d",&n,&m); if(n==0&&m==0) break; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&a[i][j]); int q,x1,x2,y1,y2; scanf("%d",&q); for(int t=0;t<q;t++) { scanf("%d%d%d%d",&x1,&y1,&x2,&y2); if(a[x1][y1]!=a[x2][y2]||a[x1][y1]==0) { printf("NO\n"); continue; } flag=0; memset(vis,0,sizeof(vis)); dfs(x1,y1,x2,y2,0,0,vis); if(flag) printf("YES\n"); else printf("NO\n"); } } return 0; }
原文：http://www.cnblogs.com/xzxj/p/7236160.html