//迷宫求解问题//思路：深度优先搜索#include <iostream>#include <math.h>using namespace std;#define max 8char map[max][max];int axisx[]={0,-1,0,1}; //代表行上的偏移int axisy[]={-1,0,1,0}; //代表列上的偏移int dx,dy;int t;int n,m;bool escape;void dfs(int sx,int sy,int cnt) //cnt代表现在已经过的时间{ if(sx == dx && sy == dy && cnt==t) { escape = true; return; } int temp = (t-cnt)-abs(sx-dx)-abs(sy-dy); if(temp<0 || temp&1) //temp<0代表剩余的时间无法走完剩余的路程 temp&1是进行奇偶剪枝 { escape = false; return; } for(int i=0;i<4;++i) { if(sx+axisx[i]<0 || sx+axisx[i]>n-1 || sy+axisy[i]<0 || sy+axisy[i]>m-1) continue; if(map[sx+axisx[i]][sy+axisy[i]]!='X') { map[sx+axisx[i]][sy+axisy[i]] = 'X'; dfs(sx+axisx[i],sy+axisy[i],cnt+1); map[sx+axisx[i]][sy+axisy[i]] = '.'; //别忘了深度优先遍历之后进行还原 } if(escape) break; }}int main(){ //freopen("1.txt","r",stdin); while(cin>>n>>m>>t && !(n==0 && m==0 && t==0)) { escape = false; int sx,sy; //sx代表sx行,sy代表sy列 int wallnum = 0; for(int i1=0;i1<n;++i1) //第i1行 { for(int i2=0;i2<m;++i2) //第i2列 { cin>>map[i1][i2]; if(map[i1][i2]=='S') { sx = i1; sy = i2; map[sx][sy] = 'X'; } else if(map[i1][i2]=='D') { dx = i1; dy = i2; } else if(map[i1][i2]=='X') wallnum++; } } if(!(n*m-wallnum<t)) //剩下的block块数小于时间则进行剪枝 { dfs(sx,sy,0); } if(escape) cout<<"YES"<<endl; else cout<<"NO"<<endl; } //fclose(stdin); return 0;}
转载于:https://www.cnblogs.com/north_dragon/archive/2010/04/25/1720686.html
相关资源：数据结构—成绩单生成器