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.
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:
‘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.
Output
For each test case, print in one line “YES” if the doggie can survive, or “NO” otherwise.
Sample Input
4 4 5
S.X.
…X.
…XD
…
3 4 5
S.X.
…X.
…D
0 0 0
Sample Output
NO
YES
翻译：
小狗在一个古老的迷宫里找到了一块骨头，这让他很着迷。然而，当他捡起它时，迷宫开始摇晃，小狗能感觉到地面在下沉。他意识到那块骨头是个陷阱，他拼命想从迷宫里出来。
迷宫是一个长方形，大小为N×M，迷宫里有一扇门。一开始，门是关着的，它会在第T秒打开一小段时间（不到1秒）。因此小狗必须在第T秒到达门口。在每秒钟，他可以移动一个街区到其中一个上，下，左，右相邻的街区。一旦他进入一个街区，这个街区的地面会在下一秒开始下沉和消失。他不能在一个街区停留超过一秒钟，也不能搬进一个参观过的街区。可怜的小狗能活下来吗？请帮帮他。
输入
输入由多个测试用例组成。每个测试用例的第一行包含三个整数N、M和T（1<N，M<7；0<T<50），分别表示迷宫的大小和门打开的时间。接下来的N行给出迷宫布局，每行包含M个字符。字符是以下内容之一：
“X”：一堵墙，小狗不能进去；
“S”：小狗的起点；
“D”：门；或
“.”：空块。
输入
以三个0终止。不处理此测试用例。
输出
对于每个测试用例，如果狗狗能活下来，在一行中打印“YES”，否则打印“NO”。
题目大意：
一扇门只能在第T秒时打开，给出了一些限制条件，问小狗是否能在开门时恰好到达这扇门，逃出去。
#include <stdio.h>
#include <string.h>
char a[80][80];
int m,n,t,flag,i,j;
int book[80][80];
int next[4][2]= {{0,1},{1,0},{0,-1},{-1,0}};//路
void dfs(int step,int x,int y)
{
int k,tx,ty;
if(a[x][y]=='D')//大门
{
if(t==step)
flag=1;
return ;
}
if(flag==1||step>=t)
return ;
for(k=0; k<4; k++)
{
tx=x+next[k][0];
ty=y+next[k][1];
if(tx<0||tx>=m||ty<0||ty>=n||a[tx][ty]=='X')//不符合条件的需要继续搜索
continue;
if(book[tx][ty]==0&&a[tx][ty]=='.'||a[tx][ty]=='D')//每符合条件都要标记
{
book[tx][ty]=1;
dfs(step+1,tx,ty);
book[tx][ty]=0;
}
}
return ;
}
int main()
{
while(~scanf("%d%d%d",&m,&n,&t))
{
flag=0;
if(n==0||m==0||t==0)
break;
//数据太多，需要初始化数组
memset(book,0,sizeof(a));
memset(book,0,sizeof(book));
for(i=0; i<m; i++)
scanf("%s",a[i]);
for(i=0; i<m; i++)
{
for(j=0; j<n; j++)
{
if(book[i][j]==0&&a[i][j]=='S')//起点，并标记
{
book[i][j]=1;
dfs(0,i,j);
break;
}
}
}
//判断条件
if(flag==1)
printf("YES
");
else
printf("NO
");
}
return 0;
}
转自：https://blog.csdn.net/wenbuxiao/article/details/107604192