究极坐牢,刚开始思路没错但是TLE了,直接套了两层bfs也难怪
以为自己终于可以自己写出来一次,还是去看别人代码调了,直接两次bfs,刚开始想到了,但是感觉不如模拟来的直观(火先走,人再走)
淦,图书馆坐了四个小时,一上午两道题,颈椎很难顶,下午去健身房了…
#include <iostream>
#include <queue>
#include <cstring>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 1010;
int t;
int n, m;
char g[N][N];
int dj[N][N], df[N][N];
PII pf, pj;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
void bfs1() {
queue<PII> qf;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (g[i][j] == 'F') {
pf.x = i, pf.y = j;
df[i][j] = 0;
qf.push(pf);
}
}
}
while (qf.size()) {
PII tf = qf.front();
qf.pop();
for (int i = 0; i < 4; i++) {
int a = tf.x + dx[i], b = tf.y + dy[i];
if (a < 0 || a > n - 1 || b < 0 || b > m - 1 || g[a][b] == '#' || df[a][b] != -1)
continue;
df[a][b] = df[tf.x][tf.y] + 1;
pf.x = a, pf.y = b;
qf.push(pf);
}
}
}
void bfs2(PII J) {
queue<PII> q;
q.push(J);
dj[J.x][J.y] = 0;
while (q.size()) {
PII t = q.front();
q.pop();
if (t.x == 0 || t.y == 0 || t.x == n - 1 || t.y == m - 1) {
printf("%d\n", dj[t.x][t.y] + 1); // 从出口出去还要加1
return;
}
for (int i = 0; i < 4; i++) {
int a = t.x + dx[i], b = t.y + dy[i];
if (g[a][b] == '#' || dj[a][b] != -1 || (df[a][b] != -1 && dj[t.x][t.y] + 1 >= df[a][b]))
continue;
dj[a][b] = dj[t.x][t.y] + 1;
pj.x = a, pj.y = b;
q.push(pj);
}
}
printf("IMPOSSIBLE\n");
}
int main() {
cin >> t;
while (t--) {
cin >> n >> m;
PII J, F;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> g[i][j];
if (g[i][j] == 'J')
J.x = i, J.y = j;
}
}
memset(dj, -1, sizeof dj);
memset(df, -1, sizeof df);
bfs1();
bfs2(J);
}
return 0;
}