#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
using namespace std;
struct node
{
int x,y,step;
node(int x,int y,int step):x(x),y(y),step(step){}
};
queue<node> q;
int T;
int n,m;
char mp[1005][1005];
int fire[1005][1005];
bool vis[1005][1005];
int bx,by;
int X[]={1,-1,0,0};
int Y[]={0,0,1,-1};
void clear()
{
while(!q.empty())
{
q.pop();
}
}
void fires()
{
while(!q.empty())
{
node f=q.front();
q.pop();
fire[f.x][f.y]=f.step;
for(int i=0;i<4;i++)
{
int xx=f.x+X[i],yy=f.y+Y[i];
if(xx>=0&&xx<n&&yy>=0&&yy<m&&fire[xx][yy]==1000000000&&mp[xx][yy]!='#')
{
q.push(node(xx,yy,f.step+1));
}
}
}
}
int ans=1000000000;
void run()
{
memset(vis,0,sizeof(vis));
clear();
q.push(node(bx,by,0));
while(!q.empty())
{
node f=q.front();
q.pop();
if(f.x==0||f.x==n-1||f.y==0||f.y==m-1)
{
ans=f.step;
return;
}
vis[f.x][f.y]=true;
for(int i=0;i<4;i++)
{
int xx=f.x+X[i],yy=f.y+Y[i];
if(xx>=0&&xx<n&&yy>=0&&yy<m&&!vis[xx][yy]&&mp[xx][yy]!='#'&&fire[xx][yy]>f.step+1)
{
q.push(node(xx,yy,f.step+1));
}
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin>>T;
while(T--)
{
ans=1000000000;
clear();
cin>>n>>m;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>mp[i][j];
fire[i][j]=1000000000;
if(mp[i][j]=='J')
{
bx=i;
by=j;
}
if(mp[i][j]=='F')
{
q.push(node(i,j,0));
}
}
}
fires();
run();
if(ans==1000000000)
{
puts("IMPOSSIBLE");
}
else
{
cout<<ans+1<<endl;
}
}
return 0;
}
关于UVa:
为什么别人的提交都可以正常地返回结果,而我的提交绑定了账号,并且在UVa查看得知已经收到了提交并且出了结果,但是在洛谷变成了UKE???