[数据结构与算法]Tempter of the Bone（白骨的诱惑者）(dfs经典模板题) HDU - 1010

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 结尾。不处理此测试用例。
输出
对于每个测试用例，如果小狗可以生存，则在一行中打印“是”，否则打印“否”。
样本输入
4 4 5
SX
…X。
…XD
…
3 4 5
SX
…X。
…D
0 0 0
样本输出
不
是的

解题思路： 一道比较经典的dfs模板题，其实本题说的能否在第T秒到达门口，就等于让你判断小狗能否刚好走了T步到达门口。本题涉及到了剪枝，不进行剪枝优化的话会超时。
本题剪枝思路：
t-s为目前剩余的时间，(abs(x-ex)+abs(y-ey))为从当前位置到终点（门)所需要的最短步数，我们知道：奇数-偶数 = 奇数，而奇数-奇数= 偶数，偶数-偶数=偶数，所以只有当剩余的时间与当前位置到终点的最短步数奇偶性相同时，才有可能恰好在t时刻到大门的地方，而由于墙的缘故，我们还需要根据题目进一步判断才能得到答案。

#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;

int n,m,t;
int sx,sy,ex,ey,flag=0;
char mp[11][11];
int book[11][11];
int Next[4][2]={{1,0},{-1,0},{0,1},{0,-1}};

void dfs(int x,int y,int s)
{
	if((t-s-(abs(x-ex)+abs(y-ey)))%2!=0) return;
	/*
	这里是本题剪枝的核心代码，可以看上面的解释多理解一下
	*/
	if(x==ex&&y==ey)
	{
		if(s==t)
		{
			flag=1;
			return ;
		}
		else return;
	}
	if(flag==1) return;//找到答案直接return出去，减少步骤。
	
	for(int i=0; i<4; i++)
	{
		int tx=x+Next[i][0];
		int ty=y+Next[i][1];
		if(tx<0||tx>n-1||ty<0||ty>m-1) continue;
		if(mp[tx][ty]=='X') continue;
		if(mp[tx][ty]=='.'&&book[tx][ty]==0)
		{
			book[tx][ty]=1;
			dfs(tx,ty,s+1);
			book[tx][ty]=0;//注意返回标记，以便下次搜索
		}
	}
	return ;
}

int main()
{
	while(cin>>n>>m>>t)
	{
		flag=0;
		if(n==0&&m==0&&t==0) break;
		memset(book,0,sizeof(book));
		memset(mp,'\0',sizeof(mp));
		for(int i=0; i<n; i++)
			for(int j=0; j<m; j++)
			{
				cin>>mp[i][j];
				if(mp[i][j]=='S')
				{
					sx=i,sy=j;
					mp[i][j]=='.';
				}
				if(mp[i][j]=='D')
				{
					ex=i,ey=j;
					mp[i][j]='.';
				}
			}//存入地图数据
		book[sx][sy]=1;//标记起始点
		dfs(sx,sy,0);
		if(flag==1) cout<<"YES"<<endl;
		else cout<<"NO"<<endl; 
	}
}