HDOJ 1010 HDU 1010 Tempter of the Bone ACM 1010 IN HDU
MiYu原創, 轉帖請注明 : 轉載自?______________白白の屋
題目地址:
?????http://acm.hdu.edu.cn/showproblem.php?pid=1010?
題目描述:
?代碼
Tempter?of?the?BoneTime?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去了.
所謂奇偶剪枝 :?
所謂路徑剪枝: ?
?? ?矩陣的大小是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;
}
另外附上一網友詳細解釋:
?
轉載于:https://www.cnblogs.com/MiYu/archive/2010/08/18/1802753.html
總結
以上是生活随笔為你收集整理的HDOJ 1010 HDU 1010 Tempter of the Bone ACM 1010 IN HDU的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： CSS 实现背景半透明
- 下一篇： Mac无法打开“XX”，因为Apple无