4179

문제 자체가 어렵지는 않은데 반례를 못 찾아서 고생을 했다....
문제 잘 읽어야 함! 고려해야할 게 많음!

접근법

매 분마다 지훈이와 불을 동시에 이동시키려고 하면 어려워진다.
전형적인 BFS 문제고 R, C 값이 1000이니 차라리 불 전부 퍼뜨리기 > 지훈이 움직이기로 BFS를 두번 시행하는 게 쉽다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int[] dr = {1, -1, 0, 0};
    static int[] dc = {0, 0, 1, -1};
    static int N, M;
    static char[][] map;
    static int[][] fireMap;
    static int[][] jMap;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new char[N][M];
        fireMap = new int[N][M];
        jMap = new int[N][M];

        Queue<int[]> fireQueue = new LinkedList<>();
        Queue<int[]> jQueue = new LinkedList<>();

        for (int i = 0; i < N; i++) {
            String line = br.readLine();
            for (int j = 0; j < M; j++) {
                map[i][j] = line.charAt(j);
                
                fireMap[i][j] = Integer.MAX_VALUE;
                jMap[i][j] = Integer.MAX_VALUE;

                if (map[i][j] == 'F') {
                    fireQueue.offer(new int[]{i, j});
                    fireMap[i][j] = 0;
                } else if (map[i][j] == 'J') {
                    jQueue.offer(new int[]{i, j});
                    jMap[i][j] = 0;
                }
            }
        }

        // 불 번지기
        while (!fireQueue.isEmpty()) {
            int[] current = fireQueue.poll();
            for (int d = 0; d < 4; d++) {
                int nr = current[0] + dr[d];
                int nc = current[1] + dc[d];

                if (nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
                if (map[nr][nc] == '#') continue;
                if (fireMap[nr][nc] <= fireMap[current[0]][current[1]] + 1) continue;

                fireMap[nr][nc] = fireMap[current[0]][current[1]] + 1;
                fireQueue.offer(new int[]{nr, nc});
            }
        }

        // 지훈이 탈출
        while (!jQueue.isEmpty()) {
            int[] current = jQueue.poll();

            // 탈출 조건 : 맵의 경계에 도달했을 때 즉시 탈출
            if (current[0] == 0 || current[0] == N - 1 || current[1] == 0 || current[1] == M - 1) {
                System.out.println(jMap[current[0]][current[1]] + 1);
                return;
            }

            for (int d = 0; d < 4; d++) {
                int nr = current[0] + dr[d];
                int nc = current[1] + dc[d];

                if (nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
                if (map[nr][nc] == '#') continue;
                // 1. 이미 더 빠른 경로로 방문했는지 확인
                if (jMap[nr][nc] <= jMap[current[0]][current[1]] + 1) continue;
                // 2. 불에 타지 않는 경로인지 확인
                if (fireMap[nr][nc] <= jMap[current[0]][current[1]] + 1) continue;

                jMap[nr][nc] = jMap[current[0]][current[1]] + 1;
                jQueue.offer(new int[]{nr, nc});
            }
        }

        System.out.println("IMPOSSIBLE");
    }
}