hdu1010 Tempter of the Bone

時間  2019-11-16 標籤 hdu1010 hdu 1010 tempter bone
  1. 轉載自：http://acm.hdu.edu.cn/forum/read.php?tid=6158
  2. sample input:
  3. 4 4 5
  4. S.X.
  5. ..X.
  6. ..XD
  7. ....
  9. 問題：
  10. (1):
  11. 在發現當前節點沒法到達時,這點彈出棧,而且把這點的標記從新刷爲'.'
  13. (2):
  14. 如何在dfs中既要保證到達又要使時間正好呢?? 在函數中經過這種形式實現:
  16. dfs(int si,int sj,int cnt) 就是用cnt來記錄當時的時間,而且在
  18. if( si==di && sj==dj && cnt==t )
  19.     {
  20.         escape = 1;
  21.         return;
  22.     }
  24. 的時候 即當前點到達了終點而且時間剛好等於題目所給限制時間時,跳出
  25. 而且escape標記爲真
  27. (3):
  28. 如何讓一個點有順序地遍歷它四周地能到達的點呢??
  29. 聰明而且簡短的方法是設施一個dir[4][2] 數組 控制方向
  30. 而且設置它的值爲dir[4][2]={{0,-1},{0,1},{1,0},{-1,0}};
  32. 遍歷的時候用for(i:0->4)就很是方便了
  34. (4):
  35. 千萬要注意的是節點越界的狀況, dfs(int si,int sj,int cnt)的時候必定要把 si, sj 控制在給你的矩陣內 在後面會提到一個個人列子 就是由於訪問了[0, -1]的位置致使了其
  37. 他數據被更改
  39. (5):
  40. 讀入矩陣的時候,能夠採用for(i = 1; i <= N; i++)
  41.                for(j = 1; j <= M; j++)
  42.                 scanf("%c", &map[i][j]);       
  44. 的方法,好處在於能夠控制和計算每個讀入的數據,壞處是調試的時候對矩陣的觀察不太方便,並且好像還會有錯誤,在2102"A計劃"用這種方法讀入數據時好像就會wa,
  46. 另外一種方法是for(i = 0; i < N; i++) gets(map[i]);
  47. 這樣讀入的數據在調試觀察的時候十分方便 gets()讀入的默認爲字符串,在vc調試的時候是顯式的 能夠直接觀察矩陣 缺點是對矩陣中各個數據的計算和控制沒法實現,須要讀完後再遍歷一遍
  49. (6)
  50. 能用bfs仍是儘可能用bfs 我不會bfs.... dfs的遞歸在調試的時候不是很方便,並且bfs要比dfs快,調試也要方便,由於它沒有遞歸
  52. (7)
  53. 關於剪枝,沒有剪枝的搜索不太可能,這題老劉上課的時候講過兩個剪枝,一個是奇偶剪枝,一個是路徑剪枝
  55. 奇偶剪枝:
  56. 把矩陣標記成以下形式:
  57. 0,1,0,1,0
  58. 1,0,1,0,1
  59. 0,1,0,1,0
  60. 1,0,1,0,1
  61. 很明顯,若是起點在0 而終點在1 那顯然 要通過奇數步才能從起點走到終點,依次類推,奇偶相同的偶數步,奇偶不一樣的奇數步
  62. 在讀入數據的時候就能夠判斷,而且作剪枝,固然作的時候並不要求把整個矩陣0,1刷一遍,讀入的時候起點記爲(Si,Sj) 終點記爲(Di,Dj) 判斷(Si+Sj) 和 (Di+Dj) 的奇偶性就能夠了
  64. 路徑剪枝:
  65. 矩陣的大小是N*M 牆的數量記爲wall 若是能走的路的數量 N*M - wall 小於時間T,就是說走完也不能到總的時間的,這顯然是錯誤的,能夠直接跳出了
  67. 課件裏面給過這題的標程,在dfs的過程當中有個沒提到的剪枝,就是記錄當前點到終點的最短路,若是小於剩餘的時間的話,就跳出
  68. 這個剪枝我以爲更科學,它畢竟是動態的麼,標程裏面是這麼寫的:
  69. temp = (t-cnt) - abs(si-di) - abs(sj-dj);
  70. if( temp<0 || temp&1 ) return;
  72. 其中求當前點到終點的最短路是這樣 abs(si-di) - abs(sj-dj) 這個就比較粗糙了 明顯沒有考慮到碰到牆要拐彎的狀況
  73. 那求最短路有沒有什麼好辦法呢?
  75. 我曾經想到過用 Dijkstraq求最短路的 ,明顯大才小用,在論壇裏看到一個方法以爲能夠用在這裏
  76. 給定下例:
  78. S.X.
  79. ..X.
  80. ..XD
  81. ....
  83. 每一個點到終點的最短路是否是這樣呢:
  85. S6X2
  86. 65X1
  87. 54XD
  88. 4321
  90. 這怎麼求呢??從終點開始遍歷整個數組,終點是0,它周圍的點都+1,牆就不計數,依次類推,就能求得這個矩陣的一個最短期矩陣,在dfs的時候比較當前點到終點的最短路,若是大於剩餘時間的話就跳出
  92. 這個方法的預處理仍是很是快的,我沒有用過,可是感受會很是有用處.
  94. (8)
  95. 在作這題的時候,我碰到過一個神奇的事情,在程序運行至下面代碼時
  97. if( map[ si+dir[i][0] ][ sj+dir[i][1] ] != 'X')           
  98.     map[ si+dir[i][0] ][ sj+dir[i][1] ] = 'X';
  100. T被改變了!! 這絲毫和T沒有關係啊,怎麼改變T的值呢??
  102. 原來在起點map[0][0]進入時,我沒有注意到map[ si+dir[i][0] ][ sj+dir[i][1] ] 實際作的是map[0][-1] = 'X'; 很危險的一個賦值,書本上千萬次強調的東西讓我碰上了,這個地方我找了好久,所以我以爲有必要單獨列出來提醒本身
  104. //////////////////////////////////////////////////////////////////////////////////////////////////////////////
  105. 下面我把一個帶註釋的標程貼一下,不是我寫的註釋
  108. //zju 2110 Tempter of the Bone
  109. #include <stdio.h>
  110. #include <iostream>
  111. #include <string.h>
  112. #include <stdlib.h>
  114. using namespace std;
  116. //迷宮地圖
  117. //X: 牆壁，小狗不能進入
  118. //S: 小狗所處的位置
  119. //D: 迷宮的門
  120. //. : 空的方格
  121. char map[9][9];
  122. int n,m,t,di,dj; //(di,dj):門的位置
  123. bool escape;
  124. int dir[4][2]={{0,-1},{0,1},{1,0},{-1,0}}; //分別表示下、上、左、右四個方向
  126. void dfs(int si,int sj,int cnt)  //表示起始位置爲(si,sj)，要求在第cnt秒達到門的位置
  127. {
  128.     int i,temp;
  129.     if( si>n || sj>m || si<=0 || sj<=0 ) return;
  130.    
  131.     if( si==di && sj==dj && cnt==t )
  132.     {
  133.         escape = 1;
  134.         return;
  135.     }
  136.    
  137.     //abs(x-ex) + abs(y - ey)表示如今所在的格子到目標格子的距離（不能走對角線）
  138.     //t-cnt是實際還須要的步數，將他們作差
  139.     //若是temp < 0或者temp爲奇數，那就不可能到達！
  140.     temp = (t-cnt) - abs(si-di) - abs(sj-dj);
  141.    
  142.     if( temp<0 || temp&1 ) return;
  143.    
  144.     for( i=0; i<4; i++ )
  145.     {
  146.         if( map[ si+dir[i][0] ][ sj+dir[i][1] ] != 'X')
  147.         {
  148.             map[ si+dir[i][0] ][ sj+dir[i][1] ] = 'X';
  149.                
  150.                 dfs(si+dir[i][0], sj+dir[i][1], cnt+1);
  151.            
  152.             if(escape) return;
  153.            
  154.             map[ si+dir[i][0] ][ sj+dir[i][1] ] = '.';
  155.         }
  156.     }
  157.    
  158.     return;
  159. }
  161. int main()
  162. {
  163.     int i,j,si,sj;
  164.    
  165.     while( cin >> n >> m >> t)
  166.     {
  167.         if( n==0 && m==0 && t==0 )
  168.             break;
  169.    
  170.         int wall = 0;
  171.         for( i=1; i<=n; i++ )
  172.             for( j=1; j<=m; j++ )
  173.             {
  174.                 cin >> map[i][j];
  175.                 if(map[i][j]=='S') { si=i; sj=j; }
  176.                 else if( map[i][j]=='D' ) { di=i; dj=j; }
  177.                 else if( map[i][j]=='X' ) wall++;
  178.             }
  179.            
  180.             if( n*m-wall <= t )
  181.             {
  182.                 cout << "NO" << endl;
  183.                 continue;
  184.             }
  185.            
  186.             escape = 0;
  187.             map[si][sj] = 'X';
  188.            
  189.             dfs( si, sj, 0 );
  190.            
  191.             if( escape ) cout << "YES" << endl;
  192.             else cout << "NO" << endl;
  193.     }
  194.    
  195.     return 0;
  196. }
联系我们 沪ICP备2021010478号-7