HDU 1010 Tempter of the Bone【DFS經典題+奇偶剪枝詳解】Tempter of the Bone

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 125945    Accepted Submission(s): 33969

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

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

Sample Output

NO

YES

Author

ZHANG, Zheng

Source

<a href="http://acm.hdu.edu.cn/search.php?field=problem&amp;key=ZJCPC2004&amp;source=1&amp;searchmode=source">ZJCPC2004</a>

題意：一個n*m的矩陣，老鼠的起點在矩陣中的'S'上，終點在矩陣中的'D'，其中'X'是牆，老鼠不能通過，'.'是路但是隻能通過一次，過了一次之後就不能再走這個地方了，終點D在第K秒是打開，這就要求老鼠能夠在第K秒是正好到達D點，如果不能就輸出NO，可以的話就輸出YES.

這道題可以不剪枝操作，也不會T了！

這裡說下不剪枝的技巧：為了避免多餘的邊界控制，可以從i=1,j=1開始讀迷宮，在讀之前将迷宮初始化為全部'X'，即都為牆。這樣在迷宮讀取完畢後，周圍就會自動出現一圈'X'，這樣就可以在搜尋的時候隻判斷遇到'X'就return了。

這裡貼一下深搜代碼，不管剪不剪枝，這一段是可以不用修改的。

關于奇偶剪枝

首先舉個例子，有如下4*4的迷宮，'.'為可走路段，'X'為障礙不可通過

<code>S... .... .... ...D</code>

從S到D的最短距離為兩點橫坐标差的絕對值+兩點縱坐标差的絕對值 = abs(Sx - Dx) + abs(Sy - Dy) = 6，這個應該是顯而易見的。

遇到有障礙的時候呢

<code>S.XX X.XX ...X ...D</code>

你會發現不管你怎麼繞路，最後從S到達D的距離都是最短距離+一個偶數，這個是可以證明的

而我們知道：

奇數 + 偶數 = 奇數

偶數 + 偶數 = 偶數

是以不管有多少障礙，不管繞多少路，隻要能到達目的地，走過的距離必然是跟最短距離的奇偶性是一緻的。

是以如果我們知道從S到D的最短距離為奇數，那麼當且僅當給定的步數T為奇數時，才有可能走到。如果給定的T的奇偶性與最短距離的奇偶性不一緻，那麼我們就可以直接判定這條路線永遠不可達了。

這裡還有個小技巧，我們可以使用按位與運算來簡化奇偶性的判斷。我們知道1的二進制是1，而奇數的二進制最後一位一定是1，而偶數的二進制最後一位一定是0。是以如果數字&amp;1的結果為1，那麼數字為奇數，反之為偶數。

下面給出奇偶剪枝後的main函數代碼：

是以完整的AC代碼如下：