UVA - 11624 Fire（BFS）

UVA - 11624

• 1.先求出所有格子被火覆盖的最短时间(多源bfs, 有多个火种)
• 2.再从起点开始bfs, 只要我到达这个格子的时间 严格小于 这个格子被火覆盖的时间，就能走到这个格子
• 3.走到边界的空地就返回

#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;typedef pair<int,int> PII;
const int N = 1010, INF = 0x3f3f3f3f;
const int dx[]={
    -1,0,1,0},dy[]={
    0,1,0,-1};char g[N][N];
int n,m,d[N][N],w[N][N];
vector<PII> fire;void bfs()
{
    memset(d,0x3f,sizeof d);queue<PII> q;for(auto &p:fire) q.push({
    p.first,p.second}), d[p.first][p.second]=0;while(q.size()){
    PII t=q.front();q.pop();for(int i=0;i<4;i++){
    int a=t.first+dx[i],b=t.second+dy[i];if(a<1||a>n||b<1||b>m) continue;if(d[a][b]!=INF||g[a][b]!='.') continue;d[a][b]=d[t.first][t.second]+1;q.push((PII){
    a,b});}}
}int BFS(int sx, int sy)
{
    if(sx==1||sx==n||sy==1||sy==m) return 1;memset(w,0x3f,sizeof w);queue<PII> q;q.push((PII){
    sx,sy});w[sx][sy]=0;while(q.size()){
    PII t=q.front();q.pop();for(int i=0;i<4;i++){
    int a=t.first+dx[i],b=t.second+dy[i];if(a<1||a>n||b<1||b>m) continue;if(w[a][b]!=INF||g[a][b]!='.') continue;if(w[t.first][t.second]+1>=d[a][b]) continue;w[a][b]=w[t.first][t.second]+1;if(a==1||a==n||b==1||b==m) return w[a][b]+1;q.push((PII){
    a,b});}}return -1;
}int main()
{
    int T;scanf("%d",&T);while(T--){
    scanf("%d%d",&n,&m);for (int i=1;i<=n;i++) scanf("%s",g[i]+1);fire.clear();int sx,sy;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(g[i][j]=='F') fire.push_back((PII){
    i,j});else if(g[i][j]=='J') sx=i,sy=j;bfs();int res=BFS(sx,sy);if(res==-1) puts("IMPOSSIBLE");else printf("%d\n",res);}return 0;
}