Tempter of the Bone
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 16817 Accepted Submission(s): 4693
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
題目分析 :
傳說中的 搜索題中具有里程碑意義的題目........
很好,很強大. 做過過這題大概也就明白了 搜索中的 奇偶剪枝以及路徑. 加了剪枝的直接結果就是 TLE 和 46MS AC.......
剛開始做的時候,也沒明白剪枝到底有什么作用, 所以直接敲了個DFS代碼就交了, 答案很明顯....TLE. 然后就去學習PPT去了.
所謂奇偶剪枝 :
- 把矩陣標記成如下形式:
- 0,1,0,1,0
- 1,0,1,0,1
- 0,1,0,1,0
- 1,0,1,0,1
- 很明顯,如果起點在0 而終點在1 那顯然 要經過奇數步才能從起點走到終點,依次類推,奇偶相同的偶數步,奇偶不同的奇數步
- 在讀入數據的時候就可以判斷,并且做剪枝,當然做的時候并不要求把整個矩陣0,1刷一遍,讀入的時候起點記為(Si,Sj) 終點記為(Di,Dj) 判斷(Si+Sj) 和 (Di+Dj) 的奇偶性就可以了
所謂路徑剪枝:
矩陣的大小是N*M 墻的數量記為wall 如果能走的路的數量 N*M - wall 小于時間T,就是說走完也不能到總的時間的,這顯然是錯誤的,可以直接跳出了.
另外還有就是, 當DFS深度 > T 時,顯然也不用繼續找下去了. 那狗已經掛了.
所以在經過這3次剪枝后, 時間就大大縮短了.
值得一提的是!!! 這題我WA了很久, 一直找不原因, 因為數據不一定是按嚴格矩陣排列的!! 也可能都在一行!!!! 所以 無論是 gets 還是 getchar 都錯的很冤枉.
使用 cin 和 scanf ("%s") 后 AC 了, 在此感謝 AMB神牛的幫忙.......
代碼如下:
/*
MiYu原創, 轉帖請注明 : 轉載自 ______________白白の屋
Author By : MiYu
Test : 1
Program : HDU1010
*/
#include <iostream>
#include <ctime>
using namespace std;
typedef struct pos{
int x,y;
void setPos( int a = 0,int b = 0 ){ x = a; y = b; }
}POS;
POS start,end;
const int START = 10; //看了就知道啥意思
const int DOOR = 20;
const int WALL = 0;
const int ROAR = 1;
int N = 0,M = 0,T = 0; //輸入的
int maze[11][11]; //很明顯是迷宮地圖
int d[4][2] = { { 0,1 },{ 1,0 },{ 0,-1 },{ -1,0 } };
int f = 1,roarCount = 0; //標記是否找到路 , 記錄可以走的路的個數
int DFS ( int x,int y,int n )
{
if ( n == T ) //時間用完了, 走到出口沒 ?
{
if ( x == end.x && y == end.y )
f = 0;
return 0;
}
if ( f == 0 ) //已經找到路了, 不用找了
return 0;
int t = T - n - abs( x-end.x ) - abs( y-end.y );
if ( t < 0 || t % 2 == 1 ) //不夠時間了 或 不可能走到(奇偶剪枝)
return 0;
for ( int i = 0; i != 4; ++ i )
{
if ( maze[ x+d[i][0] ][ y+d[i][1] ] != WALL ) //先看看下一步能不能走
{
maze[x+d[i][0]][y+d[i][1]] = WALL; //走過后就不能走了
DFS ( x+d[i][0], y+d[i][1], n + 1 ); //走到下一個位置
if ( f == 0 ) //已經找到路了, 不用找了
return 0;
maze[x+d[i][0]][y+d[i][1]] = ROAR; //沒找到路,回溯下
}
}
return 0;
}
void init() //在主函數一堆, 難看, 放外面了, 不解釋
{
memset ( maze, 0, sizeof ( maze ) );
f = 1, roarCount = 0;
for ( int i = 1; i <= N; ++ i )
{
char ch;
for ( int j = 1; j <= M ; ++ j )
{
cin >> ch;
switch ( ch )
{
case 'S': maze[i][j] = START; start.setPos ( i,j ); break;
case '.': maze[i][j] = ROAR; roarCount ++; break;
case 'X': maze[i][j] = WALL; break;
case 'D': maze[i][j] = DOOR; end.setPos ( i,j ); roarCount ++; break;
}
}
}
}
int main ()
{
while ( cin >> N >> M >> T, N + M + T )
{
init ();
if ( roarCount >= T ) //當然要保證能走的路比開門的時間要多
{
maze[start.x][start.y] = WALL;
DFS( start.x, start.y, 0 );
}
puts ( f == 1 ? "NO" : "YES" );
}
return 0;
}
另外附上一網友詳細解釋:
- 1010 temp of the bone
- sample input:
- 4 4 5
- S.X.
- ..X.
- ..XD
- ....
- 問題：
- (1):
- 在發現當前節點無法到達時,這點彈出棧,并且把這點的標記重新刷為'.'
- (2):
- 如何在dfs中既要保證到達又要使時間正好呢?? 在函數中通過這種形式實現:
- dfs(int si,int sj,int cnt) 就是用cnt來記錄當時的時間,并且在
- if( si==di && sj==dj && cnt==t )
- {
- escape = 1;
- return;
- }
- 的時候 即當前點到達了終點并且時間恰好等于題目所給限制時間時,跳出
- 并且escape標記為真
- (3):
- 如何讓一個點有順序地遍歷它四周地能到達的點呢??
- 聰明并且簡短的方法是設施一個dir[4][2] 數組 控制方向
- 并且設置它的值為dir[4][2]={{0,-1},{0,1},{1,0},{-1,0}};
- 遍歷的時候用for(i:0->4)就非常方便了
- (4):
- 千萬要注意的是節點越界的情況, dfs(int si,int sj,int cnt)的時候一定要把 si, sj 控制在給你的矩陣內 在后面會提到一個我的列子 就是因為訪問了[0, -1]的位置導致了其
- 他數據被更改
- (5):
- 讀入矩陣的時候,可以采用for(i = 1; i <= N; i++)
- for(j = 1; j <= M; j++)
- scanf("%c", &map[i][j]);
- 的方法,好處在于可以控制和計算每一個讀入的數據,壞處是調試的時候對矩陣的觀察不太方便,而且好像還會有錯誤,在2102"A計劃"用這種方法讀入數據時好像就會wa,
- 另一種方法是for(i = 0; i < N; i++) gets(map[i]);
- 這樣讀入的數據在調試觀察的時候十分方便 gets()讀入的默認為字符串,在vc調試的時候是顯式的 可以直接觀察矩陣 缺點是對矩陣中各個數據的計算和控制無法實現,需要讀完后再遍歷一遍
- (6)
- 能用bfs還是盡量用bfs 我不會bfs.... dfs的遞歸在調試的時候不是很方便,而且bfs要比dfs快,調試也要方便,因為它沒有遞歸
- (7)
- 關于剪枝,沒有剪枝的搜索不太可能,這題老劉上課的時候講過兩個剪枝,一個是奇偶剪枝,一個是路徑剪枝
- 奇偶剪枝:
- 把矩陣標記成如下形式:
- 0,1,0,1,0
- 1,0,1,0,1
- 0,1,0,1,0
- 1,0,1,0,1
- 很明顯,如果起點在0 而終點在1 那顯然 要經過奇數步才能從起點走到終點,依次類推,奇偶相同的偶數步,奇偶不同的奇數步
- 在讀入數據的時候就可以判斷,并且做剪枝,當然做的時候并不要求把整個矩陣0,1刷一遍,讀入的時候起點記為(Si,Sj) 終點記為(Di,Dj) 判斷(Si+Sj) 和 (Di+Dj) 的奇偶性就可以了
- 路徑剪枝:
- 矩陣的大小是N*M 墻的數量記為wall 如果能走的路的數量 N*M - wall 小于時間T,就是說走完也不能到總的時間的,這顯然是錯誤的,可以直接跳出了
- 課件里面給過這題的標程,在dfs的過程中有個沒提到的剪枝,就是記錄當前點到終點的最短路,如果小于剩余的時間的話,就跳出
- 這個剪枝我覺得更科學,它畢竟是動態的么,標程里面是這么寫的:
- temp = (t-cnt) - abs(si-di) - abs(sj-dj);
- if( temp<0 || temp&1 ) return;
- 其中求當前點到終點的最短路是這樣 abs(si-di) - abs(sj-dj) 這個就比較粗糙了 明顯沒有考慮到碰到墻要拐彎的情況
- 那求最短路有沒有什么好辦法呢?
- 我曾經想到過用 Dijkstraq求最短路的 ,明顯大才小用,在論壇里看到一個方法覺得可以用在這里
- 給定下例:
- S.X.
- ..X.
- ..XD
- ....
- 每個點到終點的最短路是不是這樣呢:
- S6X2
- 65X1
- 54XD
- 4321
- 這怎么求呢??從終點開始遍歷整個數組,終點是0,它周圍的點都+1,墻就不計數,依次類推,就能求得這個矩陣的一個最短時間矩陣,在dfs的時候比較當前點到終點的最短路,如果大于剩余時間的話就跳出
- 這個方法的預處理還是非常快的,我沒有用過,但是感覺會非常有用處.
- (8)
- 在做這題的時候,我碰到過一個神奇的事情,在程序運行至下面代碼時
- if( map[ si+dir[i][0] ][ sj+dir[i][1] ] != 'X')
- map[ si+dir[i][0] ][ sj+dir[i][1] ] = 'X';
- T被改變了!! 這絲毫和T沒有關系啊,怎么改變T的值呢??
- 原來在起點map[0][0]進入時,我沒有注意到map[ si+dir[i][0] ][ sj+dir[i][1] ] 實際做的是map[0][-1] = 'X'; 很危險的一個賦值,書本上千萬次強調的東西讓我碰上了,這個地方我找了很久,因此我覺得有必要單獨列出來提醒自己
- //////////////////////////////////////////////////////////////////////////////////////////////////////////////
- 下面我把一個帶注釋的標程貼一下,不是我寫的注釋
- //zju 2110 Tempter of the Bone
- #include <stdio.h>
- #include <iostream>
- #include <string.h>
- #include <stdlib.h>
- using namespace std;
- //迷宮地圖
- //X: 墻壁，小狗不能進入
- //S: 小狗所處的位置
- //D: 迷宮的門
- //. : 空的方格
- char map[9][9];
- int n,m,t,di,dj; //(di,dj):門的位置
- bool escape;
- int dir[4][2]={{0,-1},{0,1},{1,0},{-1,0}}; //分別表示下、上、左、右四個方向
- void dfs(int si,int sj,int cnt) //表示起始位置為(si,sj)，要求在第cnt秒達到門的位置
- {
- int i,temp;
- if( si>n || sj>m || si<=0 || sj<=0 ) return;
-
- if( si==di && sj==dj && cnt==t )
- {
- escape = 1;
- return;
- }
-
- //abs(x-ex) + abs(y - ey)表示現在所在的格子到目標格子的距離（不能走對角線）
- //t-cnt是實際還需要的步數，將他們做差
- //如果temp < 0或者temp為奇數，那就不可能到達！
- temp = (t-cnt) - abs(si-di) - abs(sj-dj);
-
- if( temp<0 || temp&1 ) return;
-
- for( i=0; i<4; i++ )
- {
- if( map[ si+dir[i][0] ][ sj+dir[i][1] ] != 'X')
- {
- map[ si+dir[i][0] ][ sj+dir[i][1] ] = 'X';
-
- dfs(si+dir[i][0], sj+dir[i][1], cnt+1);
-
- if(escape) return;
-
- map[ si+dir[i][0] ][ sj+dir[i][1] ] = '.';
- }
- }
-
- return;
- }
- int main()
- {
- int i,j,si,sj;
-
- while( cin >> n >> m >> t)
- {
- if( n==0 && m==0 && t==0 )
- break;
-
- int wall = 0;
- for( i=1; i<=n; i++ )
- for( j=1; j<=m; j++ )
- {
- cin >> map[i][j];
- if(map[i][j]=='S') { si=i; sj=j; }
- else if( map[i][j]=='D' ) { di=i; dj=j; }
- else if( map[i][j]=='X' ) wall++;
- }
-
- if( n*m-wall <= t )
- {
- cout << "NO" << endl;
- continue;
- }
-
- escape = 0;
- map[si][sj] = 'X';
-
- dfs( si, sj, 0 );
-
- if( escape ) cout << "YES" << endl;
- else cout << "NO" << endl;
- }
-
- return 0;
- }