UVA11624 Fire! —

题目链接：https://vjudge.net/problem/UVA-11624

题解：

坑点：“portions of the maze havecaught on fire”，表明了起火点不唯一。

火和人使用同一种结构体，用id来区别类型。BFS求解：首先将所有火苗入队，然后人再入队（肯定要火苗先入队，因为人要根据火当前烧到哪里来进行移动）。

对于一个尝试点：如果当前的id是人，且走出界，则逃生成功。如果没有走出界，则：

写法一（模拟过程）：如果没有走出界：如果id是火，且此地方是通道，则不管有没有vis过，都把它烧了，即把地图改为‘F’；如果id是人，且此地方是通道且没有被vis过，则进去。

写法二：其实火苗的本质作用是什么？就是禁止人vis那个地方，相当于会扩散的墙。有一点需要注意：对于一个通道，如果人比火先访问，那么其他相邻的通道，都是人先访问的（BFS的特点），所以火在扩散的时候，不用把周围也改为‘F’，直接把它标为vis，对于vis过的点，火和人都不能再访问。那么我们就不用把火和人分开来处理了：对于一个合法的尝试点，如果此点是通道，则把它标为已经vis，之后入队即可。

写法一：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 #include <vector>

 #include <queue>

 #include <stack>

 #include <map>

 #include <string>

 #include <set>

 #define ms(a,b) memset((a),(b),sizeof((a)))

 using namespace std;

 typedef long long LL;

 const int INF = 2e9;

 const LL LNF = 9e18;

 const int MOD = 1e9+;

 const int MAXN = 1e3+;

 int n, m;

 char g[MAXN][MAXN];

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

 struct node

 {

     int x, y, id, step;  //id为是人是火的标签

 };

 queue<node>que;

 int bfs()

 {

     ms(vis, );

     while(!que.empty()) que.pop();

     node now, tmp;

     for(int i = ; i<=n; i++)  //先将所有的火一次性放进队列中

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

     {

         if(g[i][j]=='F')

         {

             now.x = i; now.y = j;

             now.step = ; now.id = ;

             vis[now.x][now.y] = ;

             que.push(now);

         }

     }

     for(int i = ; i<=n; i++)  //将人放进队列中

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

     {

         if(g[i][j]=='J')

         {

             now.x = i; now.y = j;

             now.step = ; now.id = ;

             vis[now.x][now.y] = ;

             que.push(now);

         }

     }

     while(!que.empty())

     {

         now = que.front();

         que.pop();

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

         {

             tmp.x = now.x + dir[i][];

             tmp.y = now.y + dir[i][];

             tmp.step = now.step + ;

             tmp.id = now.id;

             if(tmp.id== && (tmp.x< || tmp.x>n || tmp.y< || tmp.y>m) )  //如果是人，且走出界，则逃生成功

                 return tmp.step;

             if(tmp.x>= && tmp.x<=n && tmp.y>= && tmp.y<=m)  //位置合法

             {

                 //如果是火，并且可以燃烧，不过他有没有vis过，都把它给烧了

                 if(tmp.id== && g[tmp.x][tmp.y]=='.' || g[tmp.x][tmp.y]=='J' )

                 {

                     g[tmp.x][tmp.y] = 'F';  //这个地方变成火了

                     que.push(tmp);

                 }

                 //如果是人，并且这个地方是通道可没有vis过，则可行

                 if(tmp.id== && g[tmp.x][tmp.y]=='.' && !vis[tmp.x][tmp.y])

                 {

                     vis[tmp.x][tmp.y] = ;

                     que.push(tmp);

                 }

             }

         }

     }

     return -;

 }

 int main()

 {

     int T;

     scanf("%d",&T);

     while(T--)

     {

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

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

             scanf("%s", g[i]+);

         int ans = bfs();

         if(ans==-)

             puts("IMPOSSIBLE");

         else

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

     }

 }

写法二：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 #include <vector>

 #include <queue>

 #include <stack>

 #include <map>

 #include <string>

 #include <set>

 #define ms(a,b) memset((a),(b),sizeof((a)))

 using namespace std;

 typedef long long LL;

 const int INF = 2e9;

 const LL LNF = 9e18;

 const int MOD = 1e9+;

 const int MAXN = 1e3+;  

 int n, m;

 char g[MAXN][MAXN];

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

 struct node

 {

     int x, y, id, step;

 };  

 queue<node>que;  

 int bfs()

 {

     ms(vis, );

     while(!que.empty()) que.pop();  

     node now, tmp;

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

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

     {

         if(g[i][j]=='F')

         {

             now.x = i; now.y = j;

             now.step = ; now.id = ;

             vis[now.x][now.y] = ;

             que.push(now);

         }

     }  

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

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

     {

         if(g[i][j]=='J')

         {

             now.x = i; now.y = j;

             now.step = ; now.id = ;

             vis[now.x][now.y] = ;

             que.push(now);

         }

     }  

     while(!que.empty())

     {

         now = que.front();

         que.pop();  

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

         {

             tmp.x = now.x + dir[i][];

             tmp.y = now.y + dir[i][];

             tmp.step = now.step + ;

             tmp.id = now.id;

             if(tmp.id== && (tmp.x< || tmp.x>n || tmp.y< || tmp.y>m) )  //逃生成功

                 return tmp.step;  

             if(tmp.x>= && tmp.x<=n && tmp.y>= && tmp.y<=m

                && !vis[tmp.x][tmp.y] && g[tmp.x][tmp.y]=='.' )  //如果此地方是通道且没有被vis，则把它标为vis

             {

                 vis[tmp.x][tmp.y] = ;

                 que.push(tmp);

             }

         }

     }

     return -;

 }  

 int main()

 {

     int T;

     scanf("%d",&T);

     while(T--)

     {

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

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

             scanf("%s", g[i]+);  

         int ans = bfs();

         if(ans==-)

             puts("IMPOSSIBLE");

         else

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

     }

 }

巴特西

UVA11624 Fire! —— BFS

最新文章

热门文章