 fireworks99
keep hungry keep foolish

# HDU 1010 Tempter of the Bone

### Description

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.

### 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
``````

NO

YES

### Code

``````#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
///BFS要以（ 结构体 ）形式存数据
///DFS只要两点：当前点与终点（不需结构体）
int n, m, time, now_x, now_y, ex, ey, t;
bool vis;///可改图以省略（通路访问完毕改为墙）
char mp;
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
bool flag;

///DFS无法中断，return返回的不知是哪一级，尽量不要在此函数里执行输出操作(易多次输出)
void dfs(int x, int y, int t)
{

///①检验部分
if(mp[x][y] == 'D' && t == time)
{
flag = 1;
return ;
}

///②剪枝部分
if(t >= time || flag)///超时剪枝 || 成功剪枝
return ;
if(abs(x - ex) + abs(y - ey) > time )///缺时剪枝
return ;
if(abs( time - t - abs(x - ex) - abs(y - ey) )% 2)///奇偶剪枝
return ;

///③搜索部分
for(int i = 0; i < 4; ++i)
{
int xx = x + dx[i];
int yy = y + dy[i];
if(x >= n || x < 0 || y >= m || y < 0 || vis[xx][yy] || mp[xx][yy] == 'X' )
continue;
vis[xx][yy] = 1;
dfs(xx, yy, t + 1);
vis[xx][yy] = 0;///取消标记，另寻他路
}
return ;
}

int main()
{
while(~scanf("%d%d%d", &n, &m, &time) && (n || m || t))
{
flag = 0;
memset(vis, 0, sizeof(vis));///两个数组都要初始化
memset(mp, 0, sizeof(mp));///我起初把初始化放在了读图的后面！

///读图
for(int i = 0; i < n; ++i)
{
scanf("%s", mp[i]);///或者cin读入
for(int j = 0; j < m; ++j)
{
if(mp[i][j] == 'S')
{
now_x = i;
now_y = j;
}
if(mp[i][j] == 'D')
{
ex = i;
ey = j;
}
}
}

///对起点的“剪枝”,相当于“刨根”吧
if(abs(now_x - ex) + abs(now_y - ey) > time || abs(time -abs(now_x - ex) - abs(now_y - ey) ) & 1 )
{
cout << "NO" << '\n';
continue;
}

vis[now_x][now_y] = 1;
dfs(now_x, now_y, 0);
if(flag)
cout << "YES" << '\n';
else
cout << "NO" << '\n';
//        for(int i = 0; i < n; ++i)
//        {
//            for(int j = 0; j < m; ++j)
//                cout << mp[i][j];
//            cout << '\n';
//        }
}
return 0;
}
``````
Site by Baole Zhao | Powered by Hexo | theme PreciousJoy