質問する

Code

#include <iostream>
#include <queue>
#include <utility>

using namespace std;

char board[1002][1002];
int dist1[1002][1002];
int dist2[1002][1002];
#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 R, C;
    queue<pair<int,int>> Q1,Q2;

    cin >> R >> C;

    for(int i=0;i<R;i++)
    {
        fill(dist1[i], dist1[i]+C, -1);
        fill(dist2[i], dist2[i]+C, -1);
        cin >> board[i];
        for(int j=0;j<C;j++)
        {
            if(board[i][j] == 'J' )
            {
                Q2.push({i,j});
                dist2[i][j] = 0;
            }else if(board[i][j] == 'F')
            {
                Q1.push({i,j});
                dist1[i][j] = 0;
            }
        }
    }
    // 불의 BFS
    while(!Q1.empty())
    {
        auto cur = Q1.front(); Q1.pop();
        for(int dir=0;dir<4;dir++)
        {
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];
            if(nx<0 || nx>=R || ny<0 || ny>=C) continue;
            if(dist1[nx][ny] != -1 || board[nx][ny] == '#') continue;
            dist1[nx][ny] = dist1[cur.X][cur.Y] + 1;
            Q1.push({nx, ny});
        }
    }
    // 지훈이의 BFS
    while(!Q2.empty())
    {
        auto cur = Q2.front(); Q2.pop();
        for(int dir=0;dir<4;dir++)
        {
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];
            if(nx<0 || nx>=R || ny<0 || ny>=C){
                cout << dist2[cur.X][cur.Y] +1;
                return 0;
            }
            if(dist2[nx][ny] != -1 || board[nx][ny] != '.') continue;
            // dist1[]도 방문 해야하는지 검사 필요
            if(dist1[nx][ny] != -1 && dist1[nx][ny] <= dist2[cur.X][cur.Y] + 1) continue;
            dist2[nx][ny] = dist2[cur.X][cur.Y] + 1;
            Q2.push({nx, ny});
        }
    }
    cout << "IMPOSSIBLE";
}

#include <string>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
using namespace std;

int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
char board[1002][1002];
int R,C;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    queue<pair<int,int>> J;
    queue<pair<int,int>> F;
    int ans=0;
    cin >> R >> C;
    for(int i=0;i<R;i++)
        for(int j=0;j<C;j++){
            cin >> board[i][j];
            if(board[i][j] == 'J') J.push({i,j});
            else if(board[i][j] == 'F') F.push({i,j});
        }
    while(!J.empty() || !F.empty())
    {
        ans++;
        queue<pair<int,int>> t2(F);
        for(int i=0;i<F.size();i++) F.pop();
        while(!t2.empty()){
            auto cur = t2.front(); t2.pop();
            for(int dir=0;dir<4;dir++){
                int ny = cur.first + dy[dir];
                int nx = cur.second + dx[dir];
                if(ny <0 || nx < 0 || ny>=R || nx>=C) continue;
                if(board[ny][nx] == '#' || board[ny][nx] == 'F') continue;
                F.push({ny, nx});
                board[ny][nx] = 'F';
            }
        }

        queue<pair<int,int>> t(J);
        for(int i=0;i<J.size();i++) J.pop();
        while(!t.empty()){
            auto cur = t.front(); t.pop();
            for(int dir=0;dir<4;dir++){
                int ny = cur.first + dy[dir];
                int nx = cur.second + dx[dir];
                /* 지훈이와 바로 붙은 벽 1칸으로는 탈출 못함 */
                if(ny <0 || nx < 0 || ny>=R || nx>=C){
                    cout << ans;
                    return 0;
                }
                if(board[ny][nx] == '.') {
                    J.push({ny, nx});
                    board[ny][nx] = 'J';
                }
            }
        }
    }
    cout << "IMPOSSIBLE";
    return 0;
}