Tempter of the Bone

Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 39780????Accepted Submission(s): 10761

原題鏈接：點擊打開鏈接
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 "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

?

Author ZHANG, Zheng

?

Source ZJCPC2004

?

Recommend JGShining
這題是求在規定時間到達出口是否可能，注意不是“規定時間內”！
使用DFS是顯然的，當然網上也有人用BFS搞出來了，不過主流還是深搜。這題的關鍵在于剪枝，不然會超時。剪枝有三個方面：
（1）統計X的個數cnt，因為走一步用一秒，所以T秒就是T步，如果N * M - cnt < T的話，可以到達的點的數量比走的步數少，則不可能到達出口。這個剪枝在這道題可以省掉很多時間（當然如果換一批測試數據效果應該就不一樣了）。
（2）第二個是很關鍵的奇偶剪枝。
假設在某一時刻t，狗狗走到P（xi, yi），又記終點為D（x0, y0）。由P到D的路徑可以分解為水平方向和豎直方向（類似于高中物理的位移的正交分解），就是說將P到D的每一條可行路徑分解為從直線x = xi到達x = x0，和由直線y = yi到直線y = y0的兩個分路徑。現在考慮由x = xi到x = x0，當x0 - xi為偶數時，說明x0和xi的奇偶性相同，那么無論通過怎么樣的路徑由x = xi到x = x0，路徑的步數總和必定為偶數（因為每走一步所處方位的x坐標奇偶性就變一次），不然不可能到達x0,，同理，當x0 - xi為奇數時，無論走什么路徑，步數總和必為奇數。考查由xi到x0之后，yi到y0的情況不言而知。設由xi到x0的步數為tx，由yi到y0的步數為ty，則tx和ty的奇偶性分別與abs(xi - x0)和abs(yi - y0)的相同，所以總步數tx + ty的奇偶性和abs(xi - x0) + abs(yi - y0)的奇偶性相同。注意，總步數tx + ty實際上就是在P點時剩余的時間t。由此可知，由P到D的總步數，也就是剩余的時間t的奇偶性必定與abs(xi - x0) + abs(yi - y0)的奇偶性相同。不然就無法從P到達D。
（3）最短路徑剪枝。
由某一點P（xi, yi）到終點D（x0, y0），最短路徑恰恰是上面提到的abs(xi - x0) + abs(yi - y0)，這也就是由P到D所需的最短時間，如果它大于當前剩余的時間，就不能到達D。

這題大概還有一個很惡心的地方是，測試數據可能會有多余的空格或換行使得就算用scanf（"%c", &c）吃掉一個換行還是會WA，我原來一直WA，拿來一個AC的程序測試了很多例子結果都是ok的，跟AC程序唯一的不同就是它把迷宮的每一行當成字符串輸入，這樣就能忽略每一行后多余的空格和換行符，而我的只是用scanf吃掉每一行的換行符。一改輸入方式立馬AC。

AC CODE：
1 #include <iostream> 2 #include <string> 3 #include <cstdio> 4 #include <cmath> 5 #include <cstring> 6 #include <algorithm> 7 #define LL long long 8 #define MAXI 2147483647 9 #define MAXL 9223372036854775807 10 #define eps (1e-8) 11 #define dg(i) cout << "*" << i << endl; 12 using namespace std; 13 14 struct Point 15 { 16 int x, y; 17 }s, d; //源點，終點 18 char map[8][8]; //迷宮地圖 19 int N, M; 20 int move[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; //方位移動 21 22 int jiou(int i, int j) 23 { 24 return abs(i - d.y) + abs(j - d.x); 25 } 26 27 bool DFS(int i, int j, int t) 28 { 29 if(!t) return 0; //時間用完 30 int a = jiou(i, j); 31 if((a & 1) != (t & 1) || a > t) return 0; //不能通過奇偶檢驗或所需時間大于剩余時間 32 int ii, jj, k; 33 for(k = 0; k < 4; k++) 34 { 35 ii = i + move[k][0]; 36 jj = j + move[k][1]; 37 if(ii > -1 && ii < N && jj > -1 && jj < M && map[ii][jj] != 'X') 38 { 39 if(map[ii][jj] == 'D' && t == 1) 40 { 41 return 1; 42 } 43 if(map[ii][jj] == '.') 44 { 45 map[ii][jj] = 'X'; 46 if(DFS(ii, jj, t - 1)) return 1; 47 map[ii][jj] = '.'; 48 } 49 } 50 } 51 return 0; 52 } 53 54 int main() 55 { 56 int i, j, T, cnt; //cnt統計X的個數 57 char c; 58 while(scanf("%d %d %d", &N, &M, &T) && N && M && T) 59 { 60 cnt = 1; 61 for(i = 0; i < N; i++) 62 { 63 scanf("%s", map[i]); 64 } 65 for(i = 0; i < N; i++) 66 { 67 for(j = 0; j < M; j++) 68 { 69 if(map[i][j] == 'X') 70 { 71 cnt++; 72 } 73 if(map[i][j] == 'S') 74 { 75 s.x = j; s.y = i; 76 map[i][j] = 'X'; 77 } 78 else if(map[i][j] == 'D') 79 { 80 d.x = j; d.y = i; 81 } 82 } 83 } 84 if(N * M - cnt < T || !DFS(s.y, s.x, T)) puts("NO"); 85 else puts("YES"); 86 } 87 return 0; 88 }

?

?

總結

以上是生活随笔為你收集整理的Tempter of the Bone（DFS + 奇偶剪枝，好题）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。