1 #include <algorithm>  2 #include <iostream>  3 #include <iomanip>  4 #include <cstring>  5 #include <climits>  6 #include <complex>  7 #include <fstream>  8 #include <cassert>  9 #include <cstdio> 10 #include <bitset> 11 #include <vector> 12 #include <deque> 13 #include <queue> 14 #include <stack> 15 #include <ctime> 16 #include <set> 17 #include <map> 18 #include <cmath> 19  20 using namespace std; 21  22 typedef pair<int, int> PII; 23 typedef struct P { 24     int x; 25     int y; 26     int s; 27     P() {} 28     P(int xx, int yy, int ss) : x(xx), y(yy), s(ss) {} 29 }P; 30  31 const int inf = 0x7f7f7f; 32 const int maxn  = 1010; 33 const int dx[4] = {0, 0, 1, -1}; 34 const int dy[4] = {1, -1, 0, 0}; 35  36 int r, c, jx, jy; 37 vector<PII> fir; 38 int ans; 39 int vis[maxn][maxn]; 40 char G[maxn][maxn]; 41  42 inline int min(int x, int y) { 43     return x < y ? x : y; 44 } 45  46 bool judge(int x, int y) { 47     if(!vis[x][y] && G[x][y] == ‘.‘ && x >= 0 && x < r && y >= 0 && y < c) { 48         return 1; 49     } 50     return 0; 51 } 52  53 bool success(int x, int y) { 54     if(G[x][y] == ‘J‘ &&  55       (x == 0 || x == r - 1 || y == 0 || y == c - 1)) { 56         return 1; 57     } 58     return 0; 59 } 60  61 void init() { 62     memset(vis, 0, sizeof(vis)); 63     memset(G, 0, sizeof(G)); 64     ans = inf;  65     fir.clear(); 66 } 67  68 void bfs() { 69     P q[maxn*maxn]; 70     int front = 0, tail = 0; 71     int fcnt = 0, jcnt = 1, tmp = 0; 72     for(int i = 0; i < fir.size(); i++) { 73         q[tail++] = P(fir[i].first, fir[i].second, 0); 74         vis[fir[i].first][fir[i].second] = 1; 75         fcnt++; 76     } 77     q[tail++] = P(jx, jy, 0); vis[jx][jy] = 1; 78     while(front < tail) { 79         for(int k = 0; k < fcnt; k++) { 80             P f = q[front++]; 81             for(int i = 0; i < 4; i++) { 82                 int xx = f.x + dx[i]; 83                 int yy = f.y + dy[i]; 84                 if(judge(xx, yy) && G[xx][yy] != ‘F‘) { 85                     vis[xx][yy] = 1; 86                     if(G[xx][yy] != ‘J‘) { 87                         G[xx][yy] = ‘F‘; 88                     } 89                     q[tail++] = P(xx, yy, f.s+1); tmp++; 90                 } 91             } 92         } 93         fcnt = tmp; tmp = 0; 94         for(int k = 0; k < jcnt; k++) { 95             P j = q[front++]; 96             if(success(j.x, j.y)) { 97                 ans = min(ans, j.s); 98             } 99             for(int i = 0; i < 4 ; i++) {100                 int xx = j.x + dx[i];101                 int yy = j.y + dy[i];102                 if(judge(xx, yy) && G[xx][yy] != ‘F‘) {103                     vis[xx][yy] = 1;104                     if(G[xx][yy] != ‘F‘) {105                         G[xx][yy] = ‘J‘;106                     }107                     q[tail++] = P(xx, yy, j.s+1); tmp++;108                 }109             }110         }111         jcnt = tmp; tmp = 0;112     }113 }114 115 int main() {116     int T;117     scanf("%d", &T);118     while(T--) {119         init();120         scanf("%d %d", &r, &c);121         for(int i = 0; i < r; i++) {122             scanf("%s", G[i]);123         }124         for(int i = 0; i < r; i++) {125             for(int j = 0; j < c; j++) {126                 if(G[i][j] == ‘J‘) {127                     jx = i; jy = j;128                 }129                 if(G[i][j] == ‘F‘) {130                     fir.push_back(PII(i, j));131                 }132             }133         }134         bfs();135         if(ans == inf) {136             printf("IMPOSSIBLE\n");137         }138         else {139             printf("%d\n", ans+1);140         }141     }142     return 0;143 }