HDU1010 Tempter of the Bone 深搜DFS-题解

● 本题解会有详细的分析，适合初学者阅读 原题

Problem Description

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; ‘.’: 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

题目翻译

Problem Description

迷宫是一个大小为N×M的矩形。迷宫里有一扇门。一开始，门是关着的，它会在第T秒打开一小段时间（不到1秒）。因此，小狗必须正好在第T秒到达门口。在每一秒钟里，他都可以移动到上、下、左、右相邻区域。一旦他进入一个区域，这个区域的地面就会开始下沉，并在下一秒消失。他不能在一个区域停留超过一秒钟，也不能进入一个已经访问过的区域。可怜的小狗能活下来吗？请帮帮他。

Input

输入由多个测试用例组成。每个测试用例的第一行包含三个整数N、M和T（1