小明在一个迷宫中。他想要出去，但是出口只是在T秒开启。其他的时间都是出于关闭的状态，所以小明只能在T秒的时候才能到达出口，小明只能在一个位置带一秒，并且不能走重复的地面，求小明能不能逃离迷宫（S:小明的起点，D出口， ‘.可以走的地面，X不能走的地地面） 输入 多实例测试 每组三个整数，n,m,t（1<n<7,0<t<50），分别代表迷宫的行数，出口开启的时间，（输入三个0的时候不处理侧测试用例） 输出 可以逃离迷宫“YES”否则输出“NO” 样例输入 4 4 5 S.X. …X. …XD … 3 4 5 S.X. …X. …D 000 样例输出 NO YES
#include<iostream> #include<math.h> using namespace std; int m,n,xb,yb,xe,ye; int dx[4]={-1,1,0,0}; int dy[4]={0,0,-1,1}; char s[105][105]; int dfs(int x,int y,int t){ if(t==0){ if(x==xe&&y==ye){ return 1; } else{ return 0; } } if((t-abs(xe-x)-abs(ye-y))%2!=0||t<(abs(xe-x)+abs(ye-y))){ return 0; } for(int i=0;i<4;i++){ int nx=x+dx[i]; int ny=y+dy[i]; if(nx<0||nx>=m||ny<0||ny>=n||s[nx][ny]=='X'){ continue; } s[nx][ny]='X'; if(dfs(nx,ny,t-1))return 1; s[nx][ny]='.'; } return 0; } int main(){ int T; while(cin>>m>>n>>T&&m&&n&&T){ for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ cin>>s[i][j]; if(s[i][j]=='S'){ xb=i; yb=j; s[i][j]='.'; } if(s[i][j]=='D'){ xe=i; ye=j; s[i][j]='.'; } } } s[xb][yb]='X'; if(dfs(xb,yb,T)){ cout<<"YES"<<endl; } else{ cout<<"NO"<<endl; } } return 0; }