题目链接:
https://vjudge.ppsucxtt.cn/problem/UVA-11624
大致题意:
迷宫里一个或多个位置有火,火没一秒蔓延到上下左右四个位置,Jor一秒只能上下左右移动一格,求Jor逃出在不遇上或逃出迷宫的最快时间。
思路:
Jor移动的方向用很多中变化,而火只会随着时间向四个方向蔓延,所以可以将Jor和火势蔓延分成两个BFS,最关键一点就是Jor到达(i,j)点时(i,j)还没有火,所以可以通过bfs_fire求出每个位置火到达的时间,只要Jor提前到达即可,因为最开始可能有多个地方有火,所以bfs_fire不是单元BFS而是多元BFS,其实多元BFS也没什么深奥的,就是最开始队列要加入多个时间为0的起点即可,而BFS_Jor只要满足到达位置时间小于火到达时间即可加入队列。
代码:
#include <iostream> #include <queue> #include <cstring> #include <algorithm> #include <cmath> #define fastio ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL) using namespace std; typedef long long ll; typedef pair<int, int> PII; const int N = 1010; const int INF = 0x3f3f3f3f; const double eps = 1e-6; const int mod = 998244353; struct node { int arrive_T, x, y; }; int dis[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; int n, m, ans, out = 0; int tim[N][N]; //存(i,j)火到达的时间 char a[N][N]; //存输入图 bool vis[N][N]; bool check(int i, int j) //判断边界条件 { if (i >= 1 && i <= n && j >= 1 && j <= m && a[i][j] != '#' && !vis[i][j]) return true; return false; } void bfs_fire() { memset(tim, INF, sizeof tim); memset(vis, false, sizeof vis); queue<node> q; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) if (a[i][j] == 'F') { vis[i][j] = true, tim[i][j] = 0; q.push({0, i, j}); } while (q.size()) { node t = q.front(); q.pop(); for (int k = 0; k < 4; k++) { int i = t.x + dis[k][0], j = t.y + dis[k][1]; if (check(i, j)) { q.push({t.arrive_T + 1, i, j}); vis[i][j] = true, tim[i][j] = t.arrive_T + 1; } } } } void bfs_Joe() { memset(vis, false, sizeof vis); queue<node> q; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) if (a[i][j] == 'J') { q.push({0, i, j}), vis[i][j] = true; break; } if (q.size()) break; } while (q.size()) { node t = q.front(); q.pop(); if (t.x == 1 || t.x == n || t.y == 1 || t.y == m) { cout << t.arrive_T + 1 << endl; out++; return; } for (int k = 0; k < 4; k++) { int i = t.x + dis[k][0], j = t.y + dis[k][1]; if (check(i, j) && t.arrive_T + 1 < tim[i][j]) //只要满足到达位置时间小于火到达时间即可加入队列 { q.push({t.arrive_T + 1, i, j}); vis[i][j] = true; } } } } int main() { fastio; int T; cin >> T; while (T--) { cin >> n >> m; ans = 0, out = 0; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> a[i][j]; bfs_fire(); bfs_Joe(); if (!out) cout << "IMPOSSIBLE" << endl; } return 0; }