-
Tempter of the Bone
Time Limit:
2000/1000 MS (Java/Others) Memory Limit:
65536/32768 K (Java/Others)
Total
Submission(s): 37935 Accepted Submission(s):
10248
/?pid=1010
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; 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
Sample Input
4 4
5
S.X.
..X.
..XD
....
3 4 5
S.X.
..X.
...D
0 0 0
Sample Output
NO
YES
题意：给出
T
，问第
T
秒是否能从
S
去到
D
百度到大牛的代码（看
cpp
就行，俺就大体讲一
下）
：
#include
using namespace std;
char map[8][8];
int r, c, ttime, x2, y2;
//ttime
是所给时间
T
，
【
r
：行、
c
：列】
bool flag;
//x2
、
y2
是
终点坐标
int x_move[4] = {0, 1,
-1, 0};
int y_move[4] = {1, 0, 0, -1};
void dfs (int x, int y, int
t)
//t
是走到当前坐标时的时刻
{
if (t > ttime)
//
超时
return
;
//
下面的
tmp
的意义：
【剩余时间
(ttim
e
-
t)(
记为
< br>left)
】与【从当前坐标
走到终点所需时间
(
abs(x-x2)
+
abs(y-y2)
)(
记为
win)
】的差，如果
tmp
是奇数，说明
left
与
wi
n
的奇偶性不同！也就是说在第
T
秒时
，不可能从当前坐标走到终点！
int tmp = ttime
- t - abs(x-x2) - abs(y-y2);
if
(tmp < 0 || tmp & 1)
//
奇偶剪枝，非常重要，很抽象
Orz...
return
for (int i = 0; i < 4; i++)
{
int tx = x + x_move[i];
int
ty = y + y_move[i];
if (tx < 0 ||
ty < 0 || tx >= r || ty >= c)
continue;