有一个n×m 大小的迷宫。其中字符’S’表示起点，字符’D’表示出口，字符’X’表示墙壁，字符’.‘表示平地。你需要从’S’出发走到’D’，每次只能向上下左右相邻的位置移动，并且不能走出地图，也不能走进墙壁。
每次移动消耗 1 时间，走过路都会塌陷，因此不能走回头路或者原地不动。现在已知出口的大门会在 T 时间打开，判断在 0 时间从起点出发能否逃离迷宫。
数据范围 n,m≤10,T≤50。只有从起点往终点搜，步数恰好等于T时，才能成立。
我们只需要DFS来搜索每条路线，并且只需要搜到T世家就可以了（可行性剪枝）。但是仅仅这样还无法通过本题，还需要更多的剪枝。
如上图所示，将n×m的网格染成黑白两色。我们记每个格子的行数和列数的和为x，如果x为偶数，那么格子就是白色，反之奇数就是黑色，容易发现两个相邻的格子颜色肯定不一样，也就是说每走一步颜色都会不一样。更普遍的结论是：走奇数步会改变颜色，走偶数步颜色不变。\n那么如果起点和终点颜色不一样，而T是奇数的话，就不可能逃离迷宫。同理，如果起点和终点颜色不一样，而T是偶数和的话，也不能逃离迷宫。遇到这两种情况时，就不用进行DFS了，直接输出“NO”。
奇数 + 偶数 = 奇数
偶数 + 偶数 = 偶数
#include <iostream> using namespace std; int qx,qy,zx,zy; int n,m; int c[4][2]={{-1,0},{0,-1},{1,0},{0,1}}; char a[55][55]; bool b[55][55]; int T; bool f; void dfs(int x,int y,int t){ int tx,ty; if(f){ return; } if(t==T){ if(a[x][y]=='D'){ f=true; } return; } b[x][y]=true; for(int i=0;i<4;i++){ tx=x+c[i][0]; ty=y+c[i][1]; if(tx>=0 && tx<n && ty>=0 && ty<m && !b[tx][ty] && a[tx][ty]!='X'){ dfs(tx,ty,t+1); } } b[x][y]=false; } int main(){ cin>>n>>m>>T; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ cin>>a[i][j]; } } for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(a[i][j]=='S'){ qx=i; qy=j; } if(a[i][j]=='D'){ zx=i; zy=j; } } } if((qx+qy+zx+zy+T)%2!=0){ //qx+qy+zx+zy是偶数证明终点和起点奇偶相同 cout<<"no"; }else{ dfs(qx,qy,0); if(f){ cout<<"yes"; }else{ cout<<"no"; } } return 0; }
