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
| #include <stdio.h>
#include <queue>
using namespace std;
char buf[1000][1001];
int dx[4] = {0,1,0,-1};
int dy[4] = {-1,0,1,0};
int M,N;
void simulation(){
int x, y,time = 1;
queue<pair<int,int>> fire;
queue<pair<int,int>> p;
for(int i = 0; i < N; ++i)
for(int j = 0; j < M; ++j)
if(buf[i][j]=='*') fire.emplace(i,j);
else if(buf[i][j]=='@') p.emplace(i,j),x=j,y=i;
if(!x||!y||x==M-1||y==N-1) {printf("1\n"); return ;}
while(!p.empty()){
int fsize = fire.size();
for(int i = 0; i < fsize; ++i){
x = fire.front().second;
y = fire.front().first;
fire.pop();
for(int j = 0; j < 4; ++j){
int nx = x + dx[j];
int ny = y + dy[j];
if(0<=nx&&nx<M&&0<=ny&&ny<N){
if(buf[ny][nx]=='.'||buf[ny][nx]=='@') buf[ny][nx]='*',fire.emplace(ny,nx);
}
}
}
int psize = p.size();
for(int i = 0; i < psize; ++i){
x = p.front().second;
y = p.front().first;
p.pop();
for(int j = 0; j < 4; ++j){
int nx = x + dx[j];
int ny = y + dy[j];
if(0<=nx&&nx<M && 0<=ny&&ny<N){
if(buf[ny][nx]=='.'){
buf[ny][nx] = '@',p.emplace(ny,nx);
if(!nx||!ny||nx==M-1||ny==N-1) {printf("%d\n",time+1); return ;}
}
}
}
}
++time;
}
printf("IMPOSSIBLE\n");
return ;
}
int main(void){
int tc;
scanf("%d",&tc);
while(tc--){
scanf("%d %d\n",&M,&N);
for(int i = 0; i < N; ++i)
scanf("%s",buf[i]);
simulation();
}
}
|
