#include <iostream>
#include <string>
#include <queue>
#include <algorithm>
using namespace std;
#define X first
#define Y second
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while(t--) {
string board[1002];
int dist[1002][1002];
int fire[1002][1002];
queue<pair<int,int>> q,qf;
int n,m;
cin >> m >> n;
//-1로 초기화 (방문 안됨)
for(int i=0; i<n;i++) {
fill(dist[i],dist[i]+m,-1);
fill(fire[i],fire[i]+m,-1);
}
//미로 입력
for(int i=0; i<n;i++) {
cin >> board[i];
}
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
//상근이 위치
if(board[i][j]=='@') {
q.push({i,j});
dist[i][j]=0;
}
//불 위치
else if(board[i][j]=='*') {
qf.push({i,j});
fire[i][j]=0;
}
}
}
//불 bfs
while(!qf.empty()) {
pair<int,int> cur=qf.front(); qf.pop();
for(int idx=0; idx<4; idx++) {
int nx=cur.X+dx[idx];
int ny=cur.Y+dy[idx];
if(nx<0 || nx>=n || ny<0 || ny>=m)continue;
if(board[nx][ny]=='#' || fire[nx][ny]>=0)continue;
fire[nx][ny]=fire[cur.X][cur.Y]+1;
qf.push({nx,ny});
}
}
int flag=0;
//상근 bfs
while(!q.empty()) {
if(flag) break;
pair<int,int> cur=q.front(); q.pop();
for(int idx=0; idx<4; idx++) {
int nx=cur.X+dx[idx];
int ny=cur.Y+dy[idx];
if(nx<0 || nx>=n || ny<0 || ny>=m) {
cout << dist[cur.X][cur.Y]+1<< '\n';
flag=1;
break;
}
//상근이가 못가는 경우
if(board[nx][ny]=='#' || dist[nx][ny]>=0)continue;
if(dist[cur.X][cur.Y]+1>=fire[nx][ny] && fire[nx][ny]!=-1 ) continue;
dist[nx][ny]=dist[cur.X][cur.Y]+1;
q.push({nx,ny});
}
}
if(!flag)cout <<"IMPOSSIBLE\n";
}
}
To embed this project on your website, copy the following code and paste it into your website's HTML: