H - Tempter of the Bone（HDU 1010）解题报告
一、原题
H - Tempter of the Bone
Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
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; 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 5S.X...X...XD....3 4 5S.X...X....D0 0 0
Sample Output
NOYES
二、题目大意：
给定一个n行，m列的矩阵，其中有四种点
'X':一个不可以走的格子
'S':起点
'D':终点
'.': 可以走的点
现规定狗狗从S点开始，走到D点，走过的点不能再走，时间限定为t，若成功输出“Yes”，不成功输出“NO”.
以0 0 0 标志数据结尾。
Ps：非常之关键的就在于要求一定要在t时刻到达D！！而不是在t时刻之内
三、基本思路：
1、基本用到的变量
二维char数组存储迷宫，对应bool二维数组存储是否被访问过
Int map[N][N];
bool visited[N][N];
int direct[4][2]= {1,0, -1,0,0,1,0,-1}; //表示四个方向
2、三个大问题：
（1）getchar（）读取结束符！
Ps：输入m,n,t后应输入迷宫，这里涉及到字符与数字混输。
由于迷宫采用一个一个读取， 应当抛弃每行末尾的回车符
（2）奇偶剪枝！
int temp=t-step-(abs(x-xd)+abs(y-yd));
//逻辑与运算判断是否为奇偶，利用的是反码补码原理
if(temp&1!=0) //剪枝：比理论上的最短距离多出来的必是偶数(或剩余时间为t,最短路径为x,那么若x和t的奇偶性必定相同)
Ps：如果不用奇偶剪枝此题必然TLE
（3）对DFS的进一步理解
利用前序遍历图去理解。这里由于DFS返回的是bool量，所以函数末尾添加一行return false。可返回到上一层的 if(dfs(x_t,y_t,step+1)) return true;处
3、DFS关键代码部分：
bool dfs(int x,int y,int step)
{
if(x==xd&&y==yd&&step==t)
return true;
if(step>t||x<=0||y<=0||x>n||y>m) //剪枝1：当step>t时还没有找到D点
return false;
int temp=t-step-(abs(x-xd)+abs(y-yd));
if(temp&1!=0) //剪枝3：比理论上的最短距离多出来的必是偶数(或剩余时间为t,最短路径为x,那么若x和t的奇偶性必定相同)
return false;
for(int i=0; i<4; i++)
{
int x_t=x+direct[i][0],y_t=y+direct[i][1];
if(!visited[x_t][y_t]&&(map[x_t][y_t]=='.'||map[x_t][y_t]=='D')&&!(step>t||x_t<=0||y_t<=0||x_t>n||y_t>m))
{
visited[x_t][y_t]=true;
if(dfs(x_t,y_t,step+1)) return true;
else visited[x_t][y_t]=false;
}
}
return false;//!
}
四、源码完整版
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>//freopen头文件
#define N 7
using namespace std;
char map[N][N];
int m,n,t;
int xs,ys,xd,yd;//表示S与D的坐标
int direct[4][2]=
{1,0,
-1,0,
0,1,
0,-1
}; //四个方向
bool visited[N][N];
bool dfs(int x,int y,int step)
{
if(x==xd&&y==yd&&step==t)
return true;
if(step>t||x<=0||y<=0||x>n||y>m) //剪枝1：当step>t时还没有找到D点
return false;
int temp=t-step-(abs(x-xd)+abs(y-yd));
if(temp&1!=0) //剪枝2：比理论上的最短距离多出来的必是偶数(或剩余时间为t,最短路径为x,那么若x和t的奇偶性必定相同)
return false;
for(int i=0; i<4; i++)
{
int x_t=x+direct[i][0],y_t=y+direct[i][1];
if(!visited[x_t][y_t]&&(map[x_t][y_t]=='.'||map[x_t][y_t]=='D')&&!(step>t||x_t<=0||y_t<=0||x_t>n||y_t>m))
{
visited[x_t][y_t]=true;
if(dfs(x_t,y_t,step+1)) return true;
else visited[x_t][y_t]=false;
}
}
return false;//啊啊啊啊啊，忘了这个WA无数次啊！
}
int main()
{
int i,j;
///freopen("in.txt","r",stdin);
while(cin>>n>>m>>t&&(n||m||t))
{
memset(map,0,sizeof(map));
memset(visited,0,sizeof(visited));
getchar();
for(i=1; i<=n; i++)
{
for(j=1; j<=m; j++)
{
cin>>map[i][j];
if(map[i][j]=='S')
{
xs=i;
ys=j;
}
if(map[i][j]=='D')
{
xd=i;
yd=j;
}
}
getchar();
}
visited[xs][ys]=true;//S已被访问
if(dfs(xs,ys,0))
cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
}
PS：典型度极高的一题，表示做完之后收获最大。强烈推荐一下伐。。。
另，附上链接：
http://acm.hdu.edu.cn/showproblem.php?pid=1010