[백준 c++] 4179 불!

문제 설명

https://www.acmicpc.net/problem/4179
지훈이를 미로에서 탈출시키자.
미로구성은 다음과 같다.

• #: 벽
• .: 지나갈 수 있는 공간
• J: 지훈이의 미로에서의 초기위치(1개) (지나갈 수 있는 공간)
• F: 불이 난 공간

불은 각 지점에서 네 방향으로 확산된다. 지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다. 지훈이와 불은 벽이 있는 공간은 통과하지 못한다.

입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.
다음 입력으로 R줄동안 각각의 미로 행이 주어진다.

지훈이가 불이 도달하기 전에 미로를 탈출 할 수 없는 경우 IMPOSSIBLE 을 출력한다.
지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다.

아이디어

지훈이가 지나가려면 확산되는 불보다 빨라야한다.
즉, 미로에서 불의 확산을 BFS로 구하고(1) 지훈이가 지나가는 경로를 BFS로 구하면서 (1)의 값보다 작으면 해당 지점은 지나갈 수 있다.

아이디어는 금방 나왔지만...여러 예외 처리를 놓쳐서 헤맨 문제다..
처음엔 불의 확산 경로를 저장하는 배열 f_visited을 단순히 0으로 초기화해서 사용했는데 그렇게 하면 불이 지나가지 않은 자리도 0으로 처리되어 지훈이의 경로와 비교할 때 지훈이가 지나갈 수 없게 처리된다.
따라서 f_visited를 const int INF = 987654321로 초기화했다.

전체 코드

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int n, m, y, x, k, l, ret;
const int INF = 987654321;
char a[1001][1001];
int visited[1001][1001];
int f_visited[1001][1001];
int dy[4] = {1, 0, -1, 0};
int dx[4] = {0, -1, 0, 1};
queue<pair<int, int>> q;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    fill(&f_visited[0][0], &f_visited[0][0] + 1001 * 1001, INF);

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> a[i][j];
            if (a[i][j] == 'J')
            {
                k = i;
                l = j;
            }
            else if (a[i][j] == 'F')
            {
                f_visited[i][j] = 1;
                q.push({i, j});
            }
        }
    }

    while (q.size())
    {
        tie(y, x) = q.front();
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int ny = y + dy[i];
            int nx = x + dx[i];

            if (ny < 0 || nx < 0 || ny >= n || nx >= m)
                continue;
            if (a[ny][nx] == '#' || f_visited[ny][nx] != INF)
                continue;
            f_visited[ny][nx] = f_visited[y][x] + 1;
            q.push({ny, nx});
        }
    }

    visited[k][l] = 1;
    q.push({k, l});
    while (q.size())
    {
        tie(y, x) = q.front();
        q.pop();
        if (x == m - 1 || y == n - 1 || x == 0 || y == 0)
        {
            ret = visited[y][x];
            break;
        }
        for (int i = 0; i < 4; i++)
        {
            int ny = y + dy[i];
            int nx = x + dx[i];

            if (ny < 0 || nx < 0 || ny >= n || nx >= m)
                continue;
            if (a[ny][nx] == '#' || visited[ny][nx])
                continue;
            if (f_visited[ny][nx] <= visited[y][x] + 1)
                continue;
            visited[ny][nx] = visited[y][x] + 1;
            q.push({ny, nx});
        }
    }
    if (ret != 0)
        cout << ret << "\n";
    else
    {
        cout << "IMPOSSIBLE\n";
    }
}