UVA 11624 - Fire! - [BFS]

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

题意：

给出一个 n×m 的矩阵，上面有的格子能走，有的格子是墙不能走。

有若干个点是火源，火每分钟都往上下左右蔓延一格（不能越墙）。又给出一个点是Joe的出发点，他只要能在不碰到火的前提下走出该矩阵，就算逃生成功，要求最小的逃生时间。

题解：

显然可以把火和人一起扔进队列里BFS，只要初始状态的时候火比人先进队，那么往后在BFS的每一层内永远都是火比人先进队。

然后，book数组正好也可以用来被火给标记掉，可以使得当前时间下人不能走火走过格子。

AC代码：

#include
using namespace std;
const int maxn = 1003;
const int INF = 0x3f3f3f3f;
const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0,1,0,-1 };int n, m;
char tmp[maxn];
int mp[maxn][maxn];struct Node {bool fire;int x, y;int step;Node() {}Node(bool _fire, int _x, int _y, int _step) {fire = _fire;x = _x, y = _y;step = _step;}
}joe, fire[maxn*maxn];
int firecnt;int vis[maxn][maxn];
queue Q;
inline bool border(Node o) {return o.x == 1 || o.x == n || o.y == 1 || o.y == m;
}
int bfs()
{memset(vis, 0, sizeof(vis));while (!Q.empty()) Q.pop();for (int i = 1; i <= firecnt; i++){fire[i].fire = 1;fire[i].step = 0;Q.push(fire[i]);vis[fire[i].x][fire[i].y] = 1;}joe.step = joe.fire = 0;Q.push(joe);vis[joe.x][joe.y] = 1;while (!Q.empty()){Node now = Q.front(); Q.pop();if (!now.fire && border(now)) return now.step;for (int k = 0; k < 4; k++){Node nxt = Node(now.fire, now.x + dx[k], now.y + dy[k], now.step + 1);if (mp[nxt.x][nxt.y]) continue;if (vis[nxt.x][nxt.y]) continue;vis[nxt.x][nxt.y] = 1;Q.push(nxt);}}return -1;
}int main()
{int T;cin >> T;while (T--){scanf("%d%d", &n, &m);memset(mp, 1, sizeof(mp));firecnt = 0;for (int i = 1; i <= n; i++){scanf("%s", tmp + 1);for (int j = 1; j <= m; j++){if (tmp[j] == '#') mp[i][j] = 1;if (tmp[j] == '.') mp[i][j] = 0;if (tmp[j] == 'J') joe.x = i, joe.y = j, mp[i][j] = 0;if (tmp[j] == 'F') firecnt++, fire[firecnt].x = i, fire[firecnt].y = j, mp[i][j] = 0;}}int ans = bfs();if (ans == -1) printf("IMPOSSIBLE\n");else printf("%d\n", ans + 1);}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！