4179번

4179

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>

using namespace std;

char map[1000][1000];
int fireVisited[1000][1000] = {
    0,
};
int jVisited[1000][1000] = {
    0,
};
int r, c;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
vector<pair<int, int>> fireLocation;

void bfsJ(int x, int y)
{
    queue<pair<int, int>> q;
    q.push(make_pair(x, y));
    jVisited[x][y] = 1;

    while (!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        for (int i = 0; i < 4; i++)
        {
            int tmpx = x + dx[i];
            int tmpy = y + dy[i];
            if (tmpx < 0 || tmpx >= r || tmpy < 0 || tmpy >= c)
                continue;
            if (jVisited[tmpx][tmpy] == 0 && map[tmpx][tmpy] != '#' && map[tmpx][tmpy] != 'F')
            {
                jVisited[tmpx][tmpy] = jVisited[x][y] + 1;
                q.push(make_pair(tmpx, tmpy));
            }
        }
    }
}

void bfsFire()
{
    queue<pair<int, int>> q;

    for (int i = 0; i < fireLocation.size(); i++)
    {
        q.push(make_pair(fireLocation[i].first, fireLocation[i].second));
        fireVisited[fireLocation[i].first][fireLocation[i].second] = 1;
    }

    while (!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        for (int i = 0; i < 4; i++)
        {
            int tmpx = x + dx[i];
            int tmpy = y + dy[i];
            if (tmpx < 0 || tmpx >= r || tmpy < 0 || tmpy >= c)
                continue;
            if (fireVisited[tmpx][tmpy] == 0 && map[tmpx][tmpy] != '#' && map[tmpx][tmpy] != 'F')
            {
                fireVisited[tmpx][tmpy] = fireVisited[x][y] + 1;
                q.push(make_pair(tmpx, tmpy));
            }
        }
    }
}

int returnAnswer()
{
    int answer = 987654321;
    for (int i = 0; i < r; i++)
    {
        if (fireVisited[i][0] != 0 && jVisited[i][0] != 0)
        {
            if (jVisited[i][0] < fireVisited[i][0])
                answer = min(answer, jVisited[i][0]);
        }
        if (fireVisited[i][c - 1] != 0 && jVisited[i][c - 1] != 0)
        {
            if (jVisited[i][c - 1] < fireVisited[i][c - 1])
                answer = min(answer, jVisited[i][c - 1]);
        }

        if (jVisited[i][0] != 0 && fireLocation.size() == 0)
        {
            answer = min(answer, jVisited[i][0]);
        }
        if (jVisited[i][c - 1] != 0 && fireLocation.size() == 0)
        {
            answer = min(answer, jVisited[i][c - 1]);
        }
    }

    for (int i = 0; i < c; i++)
    {
        if (fireVisited[0][i] != 0 && jVisited[0][i] != 0)
        {
            if (jVisited[0][i] < fireVisited[0][i])
                answer = min(answer, jVisited[0][i]);
        }
        if (fireVisited[r - 1][i] != 0 && jVisited[r - 1][i] != 0)
        {
            if (jVisited[r - 1][i] < fireVisited[r - 1][i])
                answer = min(answer, jVisited[r - 1][i]);
        }

        if (jVisited[0][i] != 0 && fireLocation.size() == 0)
        {
            answer = min(answer, jVisited[0][i]);
        }
        if (jVisited[r - 1][i] != 0 && fireLocation.size() == 0)
        {
            answer = min(answer, jVisited[r - 1][i]);
        }
    }
    return answer;
}

int main()
{
    int x, y;
    cin >> r >> c;
    for (int i = 0; i < r; i++)
    {
        cin >> map[i];

        for (int j = 0; j < c; j++)
        {
            if (map[i][j] == 'J')
            {
                x = i;
                y = j;
            }
            else if (map[i][j] == 'F')
            {
                fireLocation.push_back(make_pair(i, j));
            }
        }
    }
    bfsJ(x, y);
    bfsFire();

    int answer = returnAnswer();
    if (answer == 987654321)
        cout << "IMPOSSIBLE";
    else
        cout << answer;
}