小明做了一个很久很久的梦，醒来后他竟发现自己和朋友在一个摇摇欲坠的大棋盘上，他们必须得想尽一切办法逃离这里。 经过长时间的打探，小明发现，自己所在的棋盘格子上有个机关，上面写着“你只有一次机会，出发后t秒大门会为你敞开”，而他自己所在的棋盘是大小为 N*M 的长方形，他可以向上下左右四个方向移动（不可走有障碍点）。棋盘中有一扇门。根据机关的提示，小明顿时明白了，他和朋友必须在第 t 秒到门口。而这一切，没有回头路！因为一旦他移动了，他刚才所在的点就会消失，并且他不能在一个点上停留超过一秒，不然格子会爆炸。大逃亡开始了，请问小明和朋友能安全的逃出这奇怪的棋盘吗？
Input 输入多组测试数据。每个测试用例的第一行包含三个整数 N、M 和 T ( 1 < N , M < 7 ; 0 < T < 50 )，分别表示棋盘的大小和门打开的时间。接下来的N行给出棋盘布局，每一行包含M个字符。其中 “.”: 无障碍点 “X”: 障碍点 “S”: 起点 “D”: 门
输入以 3 个 0 结束。这个测试用例不需要处理。 输入数据中的空格有些问题，请不要使用getchar()，如果一定要用可以选择scanf("%s",) 自动忽略空格
Output 对于每组样例输出一行。 如果小明能够安全逃出，输出 “YES” ，否则输出 “NO”。
Sample Input 4 4 5 S.X. …X. …XD … 3 4 5 S.X. …X. …D 0 0 0 Sample Output NO YES Time limit1000 ms Memory limit32768 kB OS Windows 这道题只用简单dfs会超时，需要剪枝，条件剪枝和奇偶性剪枝，
#include<cstdio> #include<cstring> #include<cmath> using namespace std; char s[8][8]; int vis[8][8]; int ans; int d[4][2]={0,1,1,0,0,-1,-1,0}; int m,n,t,ex,ey; void dfs(int x,int y,int step){ if(ans) return;//也可以在下面xx和yy判定时加上条件！ans，否则也会超时 if(step>t){//当步数超过t时，一定不可行 return; } if((t-step)%2!=(abs(x-ex)+abs(y-ey))%2) return;//因为二维两个对角坐标中间的步数的奇偶性是有规律的，所以通过判断剩余的步数的奇偶性进行剪枝 if(t-step-abs(x-ex)-abs(y-ey)<0) return;//剩余的步数不足以从x，y点到达终点，则进行剪枝 if(s[x][y]=='D'&&step==t){ ans=1; return; } for(int i=0;i<4;i++){ int xx=x+d[i][0]; int yy=y+d[i][1]; if(xx>=0&&xx<n&&yy>=0&&yy<m&&!vis[xx][yy]){ vis[xx][yy]=1; dfs(xx,yy,step+1); vis[xx][yy]=0; } } } int main(){ //ios::sync_with_stdio(0); //cin.tie(),cout.tie(); while(scanf("%d %d %d",&n,&m,&t)&&(n||m||t)){ ans=0; memset(vis,0,sizeof(vis)); int dx,dy; for(int i=0;i<n;i++){ scanf("%s",s[i]); } for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ //cin>>s[i][j]; if(s[i][j]=='S'){ dx=i; dy=j; } if(s[i][j]=='D'){ ex=i; ey=j; } if(s[i][j]=='X'){ vis[i][j]=1; } } } vis[dx][dy]=1; dfs(dx,dy,0); if(ans) printf("YES\n"); else printf("NO\n"); } return 0; }