网格图里的问题首先想到BFS！！！
这里相当于一个在跑一个在追，所以要做两遍BFS
然后就是各种细节坑，建议多组数据的时候每新开一个变量的时候都要记住初始化
1 #include <cstdio> 2 #include <cmath> 3 #include <cstring> 4 #include <cstdlib> 5 #include <queue> 6 #include <stack> 7 #include <vector> 8 #include <iostream> 9 #include "algorithm" 10 using namespace std; 11 const int MAX=1005; 12 int t,n,m,ans; 13 char s[MAX][MAX]; 14 int num,xx,yy,cc[MAX*MAX],vv[MAX*MAX],st[MAX][MAX]; 15 bool vis[MAX][MAX]; 16 int dx[]={1,0,-1,0}; 17 int dy[]={0,1,0,-1}; 18 struct Poi{ 19 int x,y; 20 int ste; 21 }; 22 queue <Poi> q; 23 void bfs(){ 24 int i,j; 25 Poi zt,zz; 26 memset(st,0,sizeof(st)); 27 zt.x=xx,zt.y=yy,zt.ste=1;st[xx][yy]=1; 28 while (!q.empty()) q.pop(); 29 q.push(zt); 30 while (!q.empty()){ 31 zt=q.front();q.pop(); 32 for (i=0;i<4;i++) 33 if (s[zt.x+dx[i]][zt.y+dy[i]]=='.' && st[zt.x+dx[i]][zt.y+dy[i]]==0){ 34 zz.x=zt.x+dx[i]; 35 zz.y=zt.y+dy[i]; 36 zz.ste=zt.ste+1; 37 st[zz.x][zz.y]=zz.ste; 38 q.push(zz); 39 } 40 } 41 memset(vis,false,sizeof(vis)); 42 while (!q.empty()) q.pop(); 43 for (j=1;j<=num;j++){ 44 zt.x=cc[j],zt.y=vv[j],zt.ste=1; 45 q.push(zt); 46 vis[cc[j]][vv[j]]=true; 47 } 48 while (!q.empty()){ 49 zt=q.front();q.pop(); 50 if (st[zt.x][zt.y]>=zt.ste) st[zt.x][zt.y]=0; 51 for (i=0;i<4;i++) 52 if (s[zt.x+dx[i]][zt.y+dy[i]]=='.' && !vis[zt.x+dx[i]][zt.y+dy[i]]){ 53 zz.x=zt.x+dx[i]; 54 zz.y=zt.y+dy[i]; 55 zz.ste=zt.ste+1; 56 vis[zz.x][zz.y]=true; 57 q.push(zz); 58 } 59 } 60 } 61 int main(){ 62 freopen ("fire.in","r",stdin); 63 freopen ("fire.out","w",stdout); 64 int i,j; 65 scanf("%d",&t); 66 while (t--){ 67 scanf("%d%d ",&n,&m); 68 num=0; 69 for (i=1;i<=n;i++) scanf("%s",s[i]+1); 70 for (i=1;i<=n;i++) 71 for (j=1;j<=m;j++){ 72 if (s[i][j]=='J') 73 xx=i,yy=j; 74 if (s[i][j]=='F') 75 cc[++num]=i,vv[num]=j; 76 } 77 bfs(); 78 ans=1e8; 79 for (i=1;i<=m;i++){ 80 if (s[1][i]=='.' && st[1][i]!=0) 81 ans=min(ans,st[1][i]); 82 if (s[n][i]=='.' && st[n][i]!=0) 83 ans=min(ans,st[n][i]); 84 } 85 for (i=1;i<=n;i++){ 86 if (s[i][1]=='.' && st[i][1]!=0) 87 ans=min(ans,st[i][1]); 88 if (s[i][m]=='.' && st[i][m]!=0) 89 ans=min(ans,st[i][m]); 90 } 91 if (ans!=1e8) printf("%d ",ans); 92 else printf("IMPOSSIBLE "); 93 } 94 return 0; 95 }