hdu 1072 有炸弹的迷宫 (DFS)

题意：在n×m的地图上，0表示墙，1表示空地，2表示人，3表示目的地，4表示有定时炸弹重启器。定时炸弹的时间是6，人走一步所需要的时间是1。每次可以上、下、左、右移动一格。当人走到4时如果炸弹的时间不是0，可以重新设定炸弹的时间为6。如果人走到3而炸弹的时间不为0时，成功走出。求人从2走到3的最短时间。这个题中每个结点都是可以重复访问的，但其实，炸弹重置点不要重复走，因为，走到炸弹重置点时时间就会被设置为最大时间，当重新返回时时间又设成最大，但此时已走的步数肯定增加了

Sample Input
3
3 3
2 1 1
1 1 0
1 1 3
4 8
2 1 1 0 1 1 1 0
1 0 4 1 1 0 4 1
1 0 0 0 0 0 0 1
1 1 1 4 1 1 1 3
5 8
1 2 1 1 1 1 1 4
1 0 0 0 1 0 0 1
1 4 1 0 1 1 0 1
1 0 0 0 0 3 0 1
1 1 4 1 1 1 1 1

Sample Output
4
-1
13

 #include <iostream>

 #include <cstring>

 #include <cstdio>

 #include <queue>

 using namespace std;

 int n , m  ;

 int sx , sy  ;

 int  map[][] ;

 int step[][] ;

 int t[][] ;

 int MIN ;

 int dx[] = {,-,,} ;

 int dy[] = {,,,-} ;

 void dfs(int x ,int y , int len , int sum)

 {

     if (x< || y< || x>=n || y>=m || len <=  || sum >= MIN)

         return  ;

     if (map[x][y] == )

         return ;

     if (map[x][y] == )

     {

         if (sum < MIN)

             MIN = sum ;

         return ;

     }

     if (map[x][y] == )

         len =  ;

     if (sum >= step[x][y] && len <=t[x][y] ) //如果转了一圈 又转回来了 就要剪掉

         return ;

     step[x][y] = sum ; //当前步数

     t[x][y] = len ;    //剩余时间

     int fx , fy ;

     for(int i =  ; i <  ; i++)

     {

         fx = x + dx[i] ;

         fy = y + dy[i] ;

         dfs(fx,fy,len-,sum+) ;

     }

 }

 int main ()

 {

    // freopen("in.txt","r",stdin) ;

     int T ;

     scanf("%d" , &T) ;

     while (T--)

     {

          scanf("%d %d" , &n , &m) ;

          for (int i =  ; i < n ; i++)

             for (int j =  ; j < m ; j++)

          {

              cin>>map[i][j] ;

              step[i][j] = INT_MAX ;

              if (map[i][j] == )

              {

                  sx = i ;

                  sy = j ;

              }

          }

          memset(t ,  ,sizeof(t)) ;

          MIN = INT_MAX ;

          int len =  ;

          int sum =  ;

          dfs(sx,sy,len,sum) ;

          if (MIN == INT_MAX)

             printf("-1\n") ;

          else

             printf("%d\n" , MIN) ;

     }

     return  ;

 }