hdu1072 Nightmare---BFS

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=1072

题目大意：

在n×m的地图上，0表示墙，1表示空地，2表示人，3表示目的地，4表示有定时炸弹重启器。定时炸弹的时间是6，人走一步所需要的时间是1。每次可以上、下、左、右移动一格。当人走到4时如果炸弹的时间不是0，可以重新设定炸弹的时间为6。如果人走到3而炸弹的时间不为0时，成功走出。求人从2走到3的最短时间。

思路：

从起点进行BFS，每个节点有四个属性，x，y，step（当前步数），time（剩余时间）

由于每个节点可以多次访问，所以BFS时的vis数组失效，但是每个炸弹重启器的点必须是第一次到达才是最优解，因为每次到该点，可以time变为6，可以再走6步，要是再次回来也只能和之前一样最多走6步，一定不是最优解。所以对每个炸弹重启点进行vis标记。每走一步step+1，time-1

 #include<iostream>

 #include<queue>

 using namespace std;

 int n, m;

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

 struct node

 {

     int x, y, time, step;//time表示炸弹剩余时间，step表示当前步数

     node(){

     }

     node(int x, int y, int time, int step):x(x), y(y), time(time), step(step){

     }

 };

 int x1, y1, x2, y2;

 int Map[][];

 bool judge(int x, int y)

 {

     return (x >  && x <= n && y >  && y <= m && Map[x][y] != );

 }

 int bfs()

 {

     queue<node>q;

     node now(x1, y1, , );

     q.push(now);

     while(!q.empty())

     {

         node now = q.front();

         q.pop();

         //cout<<now.x<<" "<<now.y<<" "<<now.time<<" "<<now.step<<endl;

         if(Map[now.x][now.y] == )

         {

             return now.step;

         }

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

         {

             int xx = now.x + dir[i][];

             int yy = now.y + dir[i][];

             if(!judge(xx, yy))continue;

             int step = now.step + ;

             int time = now.time - ;

             if(time <= )continue;

             if(Map[xx][yy] == )time = , Map[xx][yy] = ;//如果走到了时间调整器，就恢复时间，并且标记该点变成0，使得不能再走

             q.push(node(xx, yy, time, step));

         }

     }

     return -;

 }

 int main()

 {

     int T;

     cin >> T;

     while(T--)

     {

         cin >> n >> m;

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

         {

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

             {

                 cin >> Map[i][j];

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

                 {

                     x1 = i, y1 = j;

                 }

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

                 {

                     x2 = i, y2 = j;

                 }

             }

         }

         cout<<bfs()<<endl;;

     }

     return ;

 }

巴特西

hdu1072 Nightmare---BFS

最新文章

热门文章