思路：两遍BFS即可,先跑Fire，再跑J。貌似写过
stp数组没有考虑初始INF！
#include<bits/stdc++.h> using namespace std; typedef pair<int,int> piir; typedef long long ll; const int maxn = 1e3+5; const int INF = 0x3f3f3f3f; struct node{ int x,y,step; }; int dx[]={1,-1,0,0},dy[]={0,0,1,-1}; char mp[maxn][maxn]; int n,m; bool vis[maxn][maxn]; int stp [maxn][maxn]; queue<node> q; bool check(node nd){ int x=nd.x,y=nd.y; if(x>=0&&x<n&&y>=0&&y<m&&mp[x][y]=='.'&&vis[x][y]==0) return 1; return 0; } void bfs1(){ //get fire step; memset(vis,0,sizeof(vis)); memset(stp,INF,sizeof(stp)); while(!q.empty()) q.pop(); for(int i=0;i<n;i++) for(int j=0;j<m;j++) if(mp[i][j]=='F') q.push(node{i,j,1}),vis[i][j]=1; node cur,tmp; while(!q.empty()){ cur = q.front(),q.pop(); for(int i=0;i<4;i++){ tmp.x = cur.x + dx[i]; tmp.y = cur.y + dy[i]; if(check(tmp)){ tmp.step = cur.step+1; q.push(tmp); stp[tmp.x][tmp.y] = tmp.step; vis[tmp.x][tmp.y] = 1; } } } } int bfs2(){ memset(vis,0,sizeof(vis)); while(!q.empty()) q.pop(); for(int i=0;i<n;i++) for(int j=0;j<m;j++) if(mp[i][j]=='J') { if(i==0||i==n-1||j==0||j==-1) return 1; q.push(node{i,j,1}),vis[i][j]=1; } node cur,tmp; while(!q.empty()){ cur = q.front(),q.pop(); for(int i=0;i<4;i++){ tmp.x = cur.x + dx[i]; tmp.y = cur.y + dy[i]; tmp.step = cur.step+1; if(check(tmp) && tmp.step < stp[tmp.x][tmp.y]){ if(tmp.x==0||tmp.x==n-1||tmp.y==0||tmp.y==m-1) return tmp.step; q.push(tmp); vis[tmp.x][tmp.y] = 1; } } } return -1; } void debug(){ for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ printf("%d ",stp[i][j]); } printf("\n"); } } int main(){ //freopen("in.txt","r",stdin); int T; scanf("%d",&T); while(T--){ scanf("%d%d",&n,&m); for(int i=0;i<n;i++){ scanf("%s",mp[i]); } bfs1(); //debug(); int ans = bfs2(); if(ans == -1) printf("IMPOSSIBLE\n"); else printf("%d\n",ans); } return 0; }
