The doggie found a bone in an ancient maze, which fascinated him a lot. However, when he picked it up, the maze began to shake, and the doggie could feel the ground sinking. He realized that the bone was a trap, and he tried desperately to get out of this maze.
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.
小狗在一个古老的迷宫中发现了一根骨头，这使它很是着迷。然而，当它捡起那根骨头的时候，迷宫开始摇晃，小狗能感受到地面在下沉。他意识到那块骨头是一个陷阱，他拼命地想要逃出这个迷宫。
迷宫是一个大小为N×m的长方形，迷宫中有一扇门。一开始，门是关着的，第t秒就会打开一段时间(少于1秒)。所以小狗必须在第t秒到达门口。在每一秒钟，他均可以移动一个街区到一个上、下、左、右相邻的街区。一旦他进入一个街区，这个街区的地面就会开始下沉，并在接下来的一秒消失。他不能在一个街区停留超过一秒钟，也不能搬进一个参观过的街区。可怜的小狗能活下来吗?请帮助他。c++
Input
The input consists of multiple test cases. The first line of each test case contains three integers N, M, and T (1 < N, M < 7; 0 < T < 50), which denote the sizes of the maze and the time at which the door will open, respectively. The next N lines give the maze layout, with each line containing M characters. A character is one of the following:
输入由多个测试用例组成。每一个测试用例的第一行包含三个整数N、M和T (1 < N, M < 7;0 < T < 50)，分别表示迷宫的大小和门打开的时间。接下来的N行给出了迷宫布局，每一行包含M个字符。一个角色是如下其中之一:web
‘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.
“X”:一堵墙，小狗进不去;
S:狗的起点;
’ D ':门;或
”。”:一个空的块。
输入以三个0结束。这个测试用例不会被处理。app
Output
For each test case, print in one line “YES” if the doggie can survive, or “NO” otherwise.
对于每一个测试用例，打印在一行“YES”，若是狗狗能够生存，或者“NO”less
Sample Input
4 4 5
S.X.
…X.
…XD
…svg
3 4 5
S.X.
…X.
…D
0 0 0布局
Sample Output
NO
YES测试
注意：若是不回朔的话时间会超限this
#include<stdio.h>
#include<cstdio>
#include<math.h>
#include<bits/stdc++.h>
const int MAX=1000;
int ans,w,k,flag,T,tx,ty;
char a[MAX][MAX];
int vis[MAX][MAX];
int d[2][4]={{1,-1,0,0},{0,0,1,-1}};
void DFS(int x,int y,int t)
{
if(t==T&&a[x][y]=='D')
{
flag=1; return;
}
vis[x][y]=1;
// ans++;
//奇偶剪枝
int temp = T - t - (abs(x-tx)+abs(y-ty));
if(temp<0||(temp&1)) return ;
for(int i=0;i<4;i++)
{
int dx = x + d[0][i];
int dy = y + d[1][i];
if(dx>=0&&dx<k&&dy>=0&&dy<w&&vis[dx][dy]!=1&&a[dx][dy]!='X'){
DFS(dx,dy,t+1);//此处用t++错误
if(flag) return ;
vis[dx][dy]=0;
//回溯
}
}
}
int main()
{
int i,j;
while(~scanf("%d%d%d",&k,&w,&T)&&(w+k+T)!=0) //k行w列
{ memset(vis,0,sizeof(vis));
// ans=0;
flag=0;
for(i=0;i<k;i++)
{
scanf("%s",a[i]);
}
for(i=0;i<k;i++)
{
for(j=0;j<w;j++)
if(a[i][j]=='D')
{ tx=i;
ty=j;
}
}
for(i=0;i<k;i++)
{
for(j=0;j<w;j++)
if(a[i][j]=='S')
{ DFS(i,j,0);
break;
}
}
if(flag)
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
题意：小狗起始位置在‘S’处，它走一步花费一秒的时间，问它是否在‘T’时刚好出来。而且‘X’为墙，小狗过不去。code