依题意来看,我们只需在BFS过程中开两个队列。其中一个队列存火,一个队列存人。
每次保证先更新火,再更新人就行。
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int N = 1010;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
struct Node
{
int x, y, type;
};
int n, m, T;
char g[N][N];
bool st[N][N];
int bfs(Node a, vector<Node> &f)
{
queue<Node> q1, q2;
memset(st, 0, sizeof st);
q1.push(a), st[a.x][a.y] = true;
for (int i = 0; i < f.size(); ++i)
q2.push(f[i]);
while (!q1.empty())
{
//先把火全部更新
auto time = q2.front().type;
while (!q2.empty() && q2.front().type == time)
{
auto t = q2.front(); q2.pop();
for (int i = 0; i < 4; ++i)
{
int x = t.x + dx[i], y = t.y + dy[i];
if (g[x][y] == '.' && x >= 1 && x <= n && y >= 1 && y <= m)
q2.push({x, y, t.type + 1}), g[x][y] = 'F';
}
}
//再更新人的动作
time = q1.front().type;
while (!q1.empty() && q1.front().type == time)
{
auto t = q1.front(); q1.pop();
if (t.x == 1 || t.x == n || t.y == 1 || t.y == m)
return t.type + 1;
for (int i = 0; i < 4; ++i)
{
int x = t.x + dx[i], y = t.y + dy[i];
if (x >= 1 && x <= n && y >= 1 && y <= m && g[x][y] == '.' && !st[x][y])
q1.push({x, y, t.type + 1}), st[x][y] = true;
}
}
}
return -1;
}
int main()
{
cin >> T;
while (T--)
{
cin >> n >> m;
int x, y;
vector<Node> fire_place;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
{
cin >> g[i][j];
if (g[i][j] == 'J')
x = i, y = j;
else if (g[i][j] == 'F')
fire_place.push_back({i, j, 0});
}
int res = bfs({x, y, 0}, fire_place);
if (res == -1)
puts("IMPOSSIBLE");
else
printf("%d\n", res);
}
return 0;
}
大佬 我的方法不知道为什么 跟你的思想差不多 就是有一个样例过不去 不知道有没有时间帮我看一下
可以啊
能帮我看看不