Problem Description
张晨乐在一个古老的迷宫中发现了一个手机，这个手机深深地吸引了他。
然而，当他拾起手机，迷宫开始摇晃，张晨乐能感觉到地面下沉。他意识到：这个手机只是一个诱饵！于是，他不顾一切地试图冲出这个迷宫。
迷宫是一个大小为N*M的矩形，有一扇门，一开始，门是关闭的，并在第T秒打开一瞬间（小于1秒的时间）。因此，张晨乐必须刚好在第T秒钟到达门口。
每一秒，他都可以向上，下，左，右四个相邻的位置中的任意一个移动。一旦他进入一个新的地方，这个地方的地面就会开始下沉，并在下一秒消失。因此，他不能在一个地方停留超过一秒钟，也不能再进入曾经走过的地方。
请问，可怜的张晨乐能够逃出迷宫吗？
Input
输入由多个测试用例组成。
每个测试用例的第一行包含三个整数N，M和T（1 <N，M <7; 0 <T <50），分别表示迷宫的大小和门打开的时间。
接下来的N行给出迷宫布局，每行包含M个字符。
每个字符含义如下：
‘X’：不能进入的墙
‘S’：起点
‘D’：门
‘.’：可以行走的地方
输入以三个0结束，这个测试用例不被处理。
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
dfs+剪枝
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=10;
char ch[N][N];
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}},st[N][N];
bool vis[N][N];
int n,m,T;
bool pru(int x,int y,int _x,int _y)
{
if(abs(_x-x)+abs(_y-y)>T) return false;
if((x+y+T-_x-_y)%2) return false;
return true;
}
bool flag=0;
bool dfs(int x,int y,int t)
{
if(flag) return true;
if(t==T)
{
if(st[x][y]==-1) return flag=true;
return false;
}
for(int i=0;i<4;++i)
{
int xx=x+dir[i][0];
int yy=y+dir[i][1];
if(xx>=0&&xx<n&&yy>=0&&yy<m&&st[xx][yy]&&!vis[xx][yy])
{
vis[xx][yy]=1;
if(dfs(xx,yy,t+1)) return true;
vis[xx][yy]=0;
}
}
return false;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
while(cin>>n>>m>>T,n)
{
int x,y,_x,_y;
memset(ch,0,sizeof ch);
memset(st,0,sizeof st);
flag=0;
for(int i=0;i<n;++i)
for(int j=0;j<m;++j)
{
cin>>ch[i][j];
if(ch[i][j]=='S') x=i,y=j,st[i][j]=1;
else if(ch[i][j]=='D') _x=i,_y=j,st[i][j]=-1;
else if(ch[i][j]=='.') st[i][j]=1;
}
if(!pru(x,y,_x,_y))
{
cout<<"NO\n";
continue;
}
memset(vis,0,sizeof vis);
vis[x][y]=1;
if(dfs(x,y,0)) cout<<"YES\n";
else cout<<"NO\n";
}
return 0;
}