The maze was a rectangle with sizes N by M. There was a door in the maze. At the beginning, the door was closed and it would open at the T-th second for a short period of time (less than 1 second). Therefore the doggie had to arrive at the door on exactly the T-th second. In every second, he could move one block to one of the upper, lower, left and right neighboring blocks. Once he entered a block, the ground of this block would start to sink and disappear in the next second. He could not stay at one block for more than one second, nor could he move into a visited block. Can the poor doggie survive? Please help him.
'X': a block of wall, which the doggie cannot enter;
'S': the start point of the doggie;
'D': the Door; or
'.': an empty block.
The input is terminated with three 0's. This test case is not to be processed.
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
char maps[][];
int n,m,t;
int di,dj;//出口
int flag;//是否成功脱逃
int dir[][]= {{,-},{,},{,},{-,}}; //四方搜索
void DFS(int x,int y,int cnt)
{
int i,temp;
int a,b;
if (x>n || y>m || x<= || y<=)//越出边界便不搜索
{
return;
}
if (x==di && y==dj && cnt==t) //时间正好的时候才能逃生
{
flag=;
return;
}
temp=abs(t-cnt)-(abs(di-x)+abs(dj-y));
//计算当前到终点的最短路与还需要的时间差,若小于0则路径剪枝
if (temp< || temp%)//temp如果是奇数的话也要剪枝
{
return;//不符合条件
}
for (i=; i<; i++)
{
a=x+dir[i][];
b=y+dir[i][];
if (maps[a][b]!='X')
{
maps[a][b]='X';//前进方向！
DFS(a,b,cnt+);//搜索该点
if (flag)
{
return;
}
maps[a][b]='.';//后退方向！恢复现场！
}
}
return ;
}
int main()
{
int i,j;
int wall;
int si,sj;//起点
while(scanf("%d%d%d",&n,&m,&t)!=EOF)
{
if(n==&&m==&&t==)
{
break;
}
getchar();
wall=;
for(i=; i<=n; i++)
{
for(j=; j<=m; j++)
{
scanf("%c",&maps[i][j]);
if(maps[i][j]=='S')
{
si=i;
sj=j;
}
else if(maps[i][j]=='D')
{
di=i;
dj=j;
}
else if(maps[i][j]=='X')
{
wall++;
}
}
getchar();
}
if(n*m-wall<=t)//路径剪枝，当走完不含墙的迷宫都还不到t时间将不能逃生
{
printf("NO\n");
continue;
}
flag=;
maps[si][sj]='X';//刷为x
DFS(si,sj,);
if(flag)
{
printf("YES\n");
}
else
{
printf("NO\n");
}
}
return ;
}