地址：

题意：n*m迷宫，求从(0,0)到(n-1,m-1)的最少时间。'X'是墙，'.'是空地，'1'-'9'表示有怪物，消灭之需要数字对应的时间。

mark：最近一直在写搜索题。搜索题有的很费劲，但是写多也就觉得嗯，就那么回事。这题也没啥可说的，直接BFS。和最简单的BFS不同的是，判断一个过去到过的点是否可走，需要多开一个数组来记录，然后判断过去到达的时间和现在到达的时间的大小。（其实最好的方法是优先队列么。。。懒得写而已。）然后因为要求路径，还要再开一个数组记录是从哪儿转移过来的就是了。路径输出的时候用递归~。

代码：

# include 
     
       # include 
      
        int dp[110][110], prt[110][110] ; char graph[110][110] ; int q[110*110*20][2] ; int n , m ; int tab[4][2] = {
   0,1,0,-1,1,0,-1,0} ; void bfs() {
   int front = 0, rear = 1, parent ; int i, x, y, xx, yy, tt ;     q[0][0] = 0, q[0][1] = 0 ;     dp[0][0] = 0 ; while (front != rear)     {
           x = q[front][0], y = q[front][1] ;         parent = front ;         front ++ ; for (i = 0 ; i < 4 ; i++)         {
               xx = x + tab[i][0] ;             yy = y + tab[i][1] ; if (xx < 0 || xx >= n) continue ; if (yy < 0 || yy >= m) continue ; if (graph[xx][yy] == 'X') continue ;             tt = dp[x][y] + 1 ; if (graph[xx][yy] != '.') tt += graph[xx][yy]-'0' ; if (dp[xx][yy] != -1 && dp[xx][yy] <= tt) continue ;             prt[xx][yy] = parent ;             dp[xx][yy] = tt ;             q[rear][0] = xx, q[rear][1] = yy ;             rear++ ;         }     } } int output(int x, int y) {
   int i, t, idx = prt[x][y] ; if (idx == -1) return 0 ;     t = output(q[idx][0], q[idx][1]) ;     printf ("%ds:(%d,%d)->(%d,%d)\n", ++t, q[idx][0], q[idx][1],x,y) ; if (graph[x][y] != '.') for (i = 0 ; i < graph[x][y]-'0' ; i++)             printf ("%ds:FIGHT AT (%d,%d)\n", ++t, x, y) ; return t ; } int main () {
   int i ; while (~scanf ("%d %d%*c", &n, &m))     {
   for (i = 0 ; i < n ; i++)             scanf ("%s%*c", graph[i]) ;         memset (dp, -1, sizeof(dp)) ;         memset (prt, -1, sizeof(prt)) ;         bfs() ; if (dp[n-1][m-1] == -1)             puts ("God please help our poor hero.") ; else         {
               printf ("It takes %d seconds to ""reach the target " "position, let me show you the way.\n", dp[n-1][m-1]) ;             output(n-1, m-1) ;         }         puts ("FINISH") ;     } return 0 ; }