UVA_11624 Fire! 【BFS】

一、题面

略

二、题意分析

一个迷宫中，有一个人Joe和一个或多个起火点，起火点可以蔓延，人可以走动，都只能走4个方向，问人能走出去的最少步数，如果不能输出不可能。很多大佬说是两遍BFS，先一遍火，记录所有火蔓延到次位置的时间，然后再一遍BFS，让Joe去走，只要满足他到该点时，火还未蔓延至此就可以。我一开始就死磕的让火的蔓延与人走同步，但后来发现很多坑！！！后来A了，总结一下，在同步的时候其实需要控制的也是时间，只不过现在的时间是通过控制每次BFS访问的位置的个数来控制的，当Joe在某个时刻可能走的点都访问完后，那么火就蔓延一次，下一次Joe走的时候，要先判断一下，之前入队列的点是否在这一时刻还合法，然后继续访问队列中的其他点，再进行下一层的遍历。最终可得到最终结果。

三、AC代码

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <queue>

 using namespace std;

 const int MAXN = 1e3;

 int R, C;

 bool Maze[MAXN+][MAXN+];

 bool visited[MAXN+][MAXN+];

 char S[MAXN+];

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

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

 struct Point

 {

     int x, y;

     int step;

     Point(){};

     Point(int a, int b)

     {

         x = a, y = b;

     }

 };

 queue<Point> FQ;

 int BFS(Point J)

 {

     memset(visited, , sizeof(visited));

     queue<Point> JQ;

     Point tj , tf, t;

     int x, y, Cnt = J.step;

     JQ.push(J);

     while(!JQ.empty())

     {

         tj = JQ.front();

         if(tj.step > Cnt)

         {

             Cnt = tj.step;

             int L = FQ.size();

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

             {

                 t = FQ.front();

                 FQ.pop();

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

                 {

                     x = t.x + dx[j];

                     y = t.y + dy[j];

                     if(Maze[x][y] ==  && x >=  && x < R && y >=  && y < C)

                     {

                         Maze[x][y] = ;

                         FQ.push(Point(x, y));

                     }

                 }

             }

         }

         JQ.pop();

         if(Maze[tj.x][tj.y] == )

             continue;

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

         {

             t.x = tj.x + dx[i];

             t.y = tj.y + dy[i];

             t.step = tj.step+;

             if(t.x <  || t.x >= R || t.y <  || t.y >= C)

             {

                 return t.step;

             }

             if(Maze[t.x][t.y] ==  && visited[t.x][t.y] == )

             {

                 visited[t.x][t.y] = ;

                 JQ.push(t);

             }

         }

     }

     return -;

 }

 int main()

 {

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

     //freopen("output.txt", "w", stdout);

     int T, Ans;

     scanf("%d", &T);

     int K = ;

     while(T--)

     {

         K++;

         memset(Maze, , sizeof(Maze));

         while(!FQ.empty())

             FQ.pop();

         scanf("%d %d", &R, &C);

         Point J, F;

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

         {

             scanf("%s", S);

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

             {

                 if(S[j] == '#')

                     Maze[i][j] = ;

                 else if(S[j] == '.')

                     Maze[i][j] = ;

                 else if(S[j] == 'J')

                 {

                     J.x = i, J.y = j;

                     Maze[i][j] = ;

                 }

                 else if(S[j] == 'F')

                 {

                     F.x = i, F.y = j;

                     Maze[i][j] = ;

                     FQ.push(F);

                 }

             }

         }

         visited[J.x][J.y] = ;

         J.step  = ;

         Ans = BFS(J);

         if(Ans == -)

         {

             printf("IMPOSSIBLE\n");

         }

         else

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

     }

     return ;

 }

巴特西

UVA_11624 Fire! 【BFS】

一、题面

二、题意分析

三、AC代码

最新文章

热门文章