题目链接：https://cn.vjudge.net/problem/UVA-11624

一开始以为只有一个Ｆ,ＷＡ的不知所措，看了评论说有多个Ｆ

思路：将所有Ｆ入队列，进行广搜，得到Ｆ到每个‘.’的最短时间。再将人Ｊ进行广搜，得到Ｊ到每个'.'的最时间。判断人到边缘上的'.'需要的时间是否小于Ｆ到该点的时间，然后找出最短时间。

  1 #include <iostream>
  2 #include <cstring>
  3 #include <cstdio>
  4 #include <queue>
  5 #include <stack>
  6 #include <algorithm>
  7 #include <cmath>
  8 #include <map>
  9 #define mem(a,b) memset(a,b,sizeof(a));
 10 using namespace std;
 11 #define INF 0x3f3f3f3f
 12 typedef long long ll;
 13 int dir[4][2] = {0,1,0,-1,1,0,-1,0};
 14 const int maxn = 5000005;
 15 int r,c,vis1[1005][1005],vis2[1005][1005];
 16 ll sum1[1005][1005],sum2[1005][1005];
 17 string s[1005];
 18 struct NNode{
 19     int x,y;
 20     NNode(int x1,int y1):x(x1),y(y1){};
 21 };
 22 queue<NNode>Q;
 23 struct Node{
 24     ll x,y,num;
 25     Node(int x1,int y1,int n1):x(x1),y(y1),num(n1){};
 26 };
 27 void bfs1() {
 28     queue<Node>q;
 29     while(!Q.empty()){
 30     NNode T = Q.front();
 31     Q.pop();
 32     vis1[T.x][T.y] = 1;
 33     q.push(Node(T.x,T.y,0));
 34     }
 35 
 36     while(!q.empty()) {
 37         Node temp = q.front();
 38         q.pop();
 39         for(int i = 0; i < 4; i++) {
 40             int fx = temp.x + dir[i][0],fy = temp.y + dir[i][1];
 41             if(!vis1[fx][fy] && s[fx][fy] != '#' && fx >=0 && fx < r && fy >=0 && fy < c)
 42             {
 43                 vis1[fx][fy] = 1;
 44                 sum1[fx][fy] = temp.num+1;
 45                 q.push(Node(fx,fy,temp.num+1));
 46             }
 47         }
 48     }
 49 }
 50 void bfs2(int x1,int y1) {
 51     queue<Node>q;
 52     q.push(Node(x1,y1,0));
 53     sum2[x1][y1] = 0;
 54     while(!q.empty()) {
 55         Node temp = q.front();
 56         q.pop();
 57         for(int i = 0; i < 4; i++) {
 58             int fx = temp.x + dir[i][0],fy = temp.y + dir[i][1];
 59             if(!vis2[fx][fy] && s[fx][fy] == '.' && fx >=0 && fx < r && fy >=0 && fy < c)
 60             {
 61                 vis2[fx][fy] = 1;
 62                 sum2[fx][fy] = temp.num+1;
 63                 q.push(Node(fx,fy,temp.num+1));
 64             }
 65         }
 66     }
 67 }
 68 int main()
 69 {
 70     int t;
 71     cin >> t;
 72     while(t--) {
 73         mem(sum1,INF);
 74         mem(sum2,INF);
 75         mem(vis1,0);
 76         mem(vis2,0);
 77         cin >> r >> c;
 78         for(int i = 0; i < r; i++) {
 79             cin >> s[i];
 80         }
 81         for(int i = 0; i < r; i++) {
 82             for(int j = 0; j < c; j++) {
 83                 if(s[i][j] == 'J') {
 84                     vis2[i][j] = 1;
 85                     bfs2(i,j);//搜索人到每个'.'的时间
 86                 }
 87                 else if(s[i][j] == 'F') {
 88                     Q.push(NNode(i,j));//将所有Ｆ入队列
 89                 }
 90             }
 91         }
 92         bfs1();//搜索Ｆ到每个'.'的最短时间
 93         ll ans = INF;
 94         for(int i = 0;i < r;i ++) {//判断边缘第一列和最后一列的点
 95                 if((s[i][0] == '.'||s[i][0] == 'J') && vis2[i][0] && sum2[i][0] < sum1[i][0])
 96                    ans = min(ans,sum2[i][0]);
 97                 if((s[i][c-1] == '.'||s[i][c-1] == 'J') && vis2[i][c-1] && sum2[i][c-1] < sum1[i][c-1])
 98                    ans = min(ans,sum2[i][c-1]);
 99         }
100         for(int i = 0;i < c;i ++) {//判断边缘第一行和最后一行的点
101                 if((s[0][i] == '.'||s[0][i] == 'J') && vis2[0][i] && sum2[0][i] < sum1[0][i])
102                    ans = min(ans,sum2[0][i]);
103                 if((s[r-1][i] == '.'||s[r-1][i] == 'J') && vis2[r-1][i] && sum2[r-1][i] < sum1[r-1][i])
104                    ans = min(ans,sum2[r-1][i]);
105         }
106         if(ans == INF)
107         cout << "IMPOSSIBLE" << endl;
108         else
109             cout << ans+1 << endl;//答案最后要加一因为还要从边缘上的点出去
110     }
111     return 0;
112 }