迷宫型的问题，题意：输入迷宫的行数和列数，以及终点开门的时间，然后输入这个迷宫，迷宫中走过的路不能重复走。起点是S，终点是D，墙为X，问从S点出发，能否在D门开的时候正好走出去。题目意思很好理解，直接用DFS搜索就好。
不过当然直接DFS的话肯定会超时，所以这个题目的关键在于要如何剪枝了，如果搜索到边界或是步数已经超过时间了就返回搜索，这是这一类题的硬性剪枝了，一般都肯定会注意到。这个题比较特殊的在于要用到奇偶剪枝的方法来处理（好吧，其实我一开始就是超时了，然后听师哥讲了奇偶剪枝才把这题AC了= =），因为这道题要求是在终点开门的那一刻正好走到，所以可以用到奇偶剪枝。
0 1 0 1 0
1 0 1 0 1
0 1 0 1 0
1 0 1 0 1
0 1 0 1 0
假如说上面就是这个迷宫的图吧，在标为0的地方作为起点，如果规定了走奇数步，那么最后走到的位置一定是在标为1的地方而不可能是在标为0的地方。同样的，如果规定了走偶数步，最后走到的位置就一定是在标0的地方，这就是奇偶剪枝。
所以放到这个题上来看，找到S和D的位置先进行奇偶剪枝，如果不符合就可以直接判断为“NO“了。
下面是AC代码：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; char mg[10][10]; bool vis[10][10]; int n,m,t; int si,sj,ei,ej; int re,step; int dfs(int a,int b,int step) { if(re) return 0; if(step>t||a<=0||a>n||b<=0||b>m) return 0; if(mg[a][b]=='D'&&step==t) { re=1; return 0; } if(!vis[a-1][b]&&mg[a-1][b]!='X') { vis[a-1][b]=1; dfs(a-1,b,step+1); vis[a-1][b]=0; } if(!vis[a+1][b]&&mg[a+1][b]!='X') { vis[a+1][b]=1; dfs(a+1,b,step+1); vis[a+1][b]=0; } if(!vis[a][b-1]&&mg[a][b-1]!='X') { vis[a][b-1]=1; dfs(a,b-1,step+1); vis[a][b-1]=0; } if(!vis[a][b+1]&&mg[a][b+1]!='X') { vis[a][b+1]=1; dfs(a,b+1,step+1); vis[a][b+1]=0; } return 0; } int main() { int i,j; while(scanf("%d%d%d",&n,&m,&t)!=EOF) { if(n==0&&m==0&&t==0) break; memset(vis,0,sizeof(vis)); for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { cin>>mg[i][j]; if(mg[i][j]=='S') { si=i; sj=j; vis[i][j]=1; } if(mg[i][j]=='D') { ei=i; ej=j; } } } re=0; if(t%2==0) { if(((si+sj)%2==0&&(ei+ej)%2==1)||((si+sj)%2==1&&(ei+ej)%2==0)) { cout<<"NO"<<endl; continue; } } else if(t%2==1) { if(((si+sj)%2==0&&(ei+ej)%2==0)||((si+sj)%2==1&&(ei+ej)%2==1)) { cout<<"NO"<<endl; continue; } } t=dfs(si,sj,0); if(re) cout<<"YES"<<endl; else cout<<"NO"<<endl; } return 0; }
