#include<bits/stdc++.h>
#define readup ios::sync_with_stdio(0)
#define tieoff cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N=1005;
char maze[N][N];
short to[4][2]= {{0,1},{1,0},{0,-1},{-1,0}};
int n,m;
struct R
{
int x,y;
ll cnt;
R(int x_=0,int y_=0,ll cnt_=0):x(x_),y(y_),cnt(cnt_) {}
};
inline bool check(R p)
{
return p.x>=0&&p.x<n&&p.y>=0&&p.y<m;
}
int vf[1005][1005],vj[1005][1005];
void F_bfs(vector<R> S)
{
R t,pre;
queue<R> q;
for (auto &i:S) q.push(i);//vf[i.x][i.y]=1;
int x=100;
while(!q.empty()&&x--)
{
pre=q.front();
q.pop();
for(int i=0; i<4; i++)
{
t.x=pre.x+to[i][0];
t.y=pre.y+to[i][1];
if(check(t)&&(maze[t.x][t.y]=='.'||maze[t.x][t.y]=='J')&&!vf[t.x][t.y])
{
t.cnt=pre.cnt+1;
q.push(t);
vf[t.x][t.y]=t.cnt;
}
}
}
}
int J_bfs(R S)
{
R t,pre;
queue<R> q;
q.push(S);
int x=100;
while(!q.empty()&&x--)
{
pre=q.front();
q.pop();
for(int i=0; i<4; i++)
{
t.x=pre.x+to[i][0];
t.y=pre.y+to[i][1];
if(!check(t)) return t.cnt+1;
if(maze[t.x][t.y]=='.'&&!vj[t.x][t.y]&&(vf[t.x][t.y]>pre.cnt+1))
{
t.cnt=pre.cnt+1;
q.push(t);
vj[t.x][t.y]=t.cnt;
}
}
}
return -1;
}
void solve()
{
R J;
vector<R> F;
int ans=-1;
memset(vf,0,sizeof(vf));
memset(vj,0,sizeof(vj));
cin>>n>>m;
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
cin>>maze[i][j];
if(maze[i][j]=='J') J=R(i,j);
else if(maze[i][j]=='F') F.push_back(R(i,j));
}
}
F_bfs(F);
ans=J_bfs(J);
/*cout<<"火的蔓延:\n";
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
cout<<vf[i][j]<<' ';
cout<<'\n';
}
cout<<"人的走动:\n";
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
cout<<vj[i][j]<<' ';
cout<<'\n';
}*/
if(ans==-1) cout<<"IMPOSSIBLE\n";
else cout<<ans<<'\n';
}
int main()
{
readup;
//tieoff;
int t;
cin>>t;
while(t--)
solve();
return 0;
}
代码如上,拿别人代码对比过,自己捏得样例没有问题...可还是WA了,已经写了打印记录数组的代码,去了注释就可以。
UVA的判题就给个WA,啥也不知道,只好求助各位大佬了!感谢!