1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
| using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int N = 1e3+5;
char b[N][N] = {{0}};
bool vis[N][N] = {{0}};
int t[N][N] = {{0}};
int T, n, m, ans = 0;
int dx[] = { 1, -1, 0, 0};
int dy[] = { 0, 0, 1, -1};
struct F {
int x, y;
int step;
};
struct P {
int x, y;
int step;
};
queue<F> f;
void pre() {
memset(vis, 0, sizeof(vis));
while(!f.empty()) {
F tf = f.front();
f.pop();
F nf = tf;
for(int i=0; i<4; i++) {
int x = nf.x = tf.x+dx[i];
int y = nf.y = tf.y+dy[i];
if(x<0 || x>=n || y<0 || y>=m) {
continue;
}
if(!vis[x][y] && b[x][y]=='.') {
nf.step = tf.step+1;
f.push(nf);
vis[x][y] = 1;
t[x][y] = nf.step;
}
}
}
}
bool bfs(int x, int y) {
memset(vis, 0, sizeof(vis));
P sp;
sp.x = x;
sp.y = y;
sp.step = 0;
queue<P> q;
q.push(sp);
vis[x][y] = 1;
while(!q.empty()) {
P tp = q.front();
q.pop();
P np = tp;
for(int i=0; i<4; i++) {
int x = np.x = tp.x+dx[i];
int y = np.y = tp.y+dy[i];
if(x<0 || x>=n || y<0 || y>=m) {
ans = tp.step+1;
return true;
}
if(!vis[x][y] && b[x][y]=='.' && tp.step+1<t[x][y]) {
np.step = tp.step+1;
q.push(np);
vis[x][y] = 1;
}
}
}
return false;
}
int main(void) {
scanf("%d", &T);
for(int cs=1; cs<=T; cs++) {
memset(t, inf, sizeof(t));
scanf("%d%d", &n, &m);
int x, y;
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
scanf(" %c", &b[i][j]);
if(b[i][j]=='F') {
F sf;
sf.x = i;
sf.y = j;
sf.step = 0;
t[i][j] = 0;
f.push(sf);
} else if(b[i][j]=='J') {
x = i;
y = j;
}
}
}
pre();
if(bfs(x, y))
printf("%d\n", ans);
else
printf("IMPOSSIBLE\n");
}
return 0;
}
|
