原题链接:acwing.com/problem/content/submission/4227/
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
typedef pair<int,int> PII;
#define x first
#define y second
const int N=1010;
int n,m;
char g[N][N];
PII st2;
vector<PII> nums;
int dist1[N][N],dist2[N][N];
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
int ans;
void bfs1()
{
queue<PII> q;
memset(dist1,0x3f,sizeof dist1);
for(auto st1:nums)
{
q.push(st1);
dist1[st1.x][st1.y]=0;
}
while(q.size())
{
auto t=q.front();
q.pop();
for(int i=0;i<4;i++)
{
int x=dx[i]+t.x,y=dy[i]+t.y;
if(x<0||x>=n||y<0||y>=m||g[x][y]!='.') continue;
if(dist1[x][y]==0x3f3f3f3f){
dist1[x][y]=dist1[t.x][t.y]+1;
q.push({x,y});
}
}
}
}
int bfs2()
{
queue<PII> q;
q.push(st2);
memset(dist2,0x3f,sizeof dist2);
dist2[st2.x][st2.y]=0;
while(q.size())
{
auto t=q.front();
q.pop();
if(t.x==0||t.x==n-1||t.y==0||t.y==m-1){
if(dist2[t.x][t.y]+1<=dist1[t.x][t.y])
return dist2[t.x][t.y]+1;
}
for(int i=0;i<4;i++)
{
int x=dx[i]+t.x,y=dy[i]+t.y;
if(x<0||x>=n||y<0||y>=m||g[x][y]!='.') continue;
if(dist2[x][y]==0x3f3f3f3f){
if(dist2[t.x][t.y]+1>=dist1[x][y]) continue;
dist2[x][y]=dist2[t.x][t.y]+1;
q.push({x,y});
}
}
}
return -1;
}
int main()
{
int tt;
cin>>tt;
while(tt--)
{
scanf("%d%d",&n,&m);
nums.clear();
ans=0x3f3f3f3f;
for(int i=0;i<n;i++)
scanf("%s",g[i]);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
if(g[i][j]=='F') nums.push_back({i,j});
else if(g[i][j]=='J') st2={i,j};
}
bfs1();
int t=bfs2();
if(t==-1) puts("IMPOSSIBLE");
else printf("%d\n",t);
}
return 0;
}
标签:10,int,迷宫,起火,dist1,st1,st2,dist2,push
From: https://www.cnblogs.com/linearlearn/p/17281283.html