#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";
    }
}

Embed on website

To embed this project on your website, copy the following code and paste it into your website's HTML: