BOJ 4179

package boj;

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

/**
 * Created by mkhwang on 2021/04/04
 * Email : orange2652@gmail.com
 * Github : http://github.com/myeongkwonhwang
 */
public class Boj4179 {
    static int R;
    static int C;
    static String maze[][];
    static int[] dx = {1,0,-1,0};
    static int[] dy = {0,1,0,-1};
    static int[][] dist1; //불의전파시간
    static int[][] dist2; //지훈이이동시간

    //불이 있는곳은 통과하지 못하고 불이 옮겨지는 시간을 계산한다.
    //불이 옮겨지는 시간을 계산해서 시간을 넣고 그 지훈이가 도달할수있는 위치가 있는지 확인
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());

        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        int count = 0;
        Queue<Node> fireQueue = new LinkedList<>();
        Queue<Node> jQueue = new LinkedList<>();
        maze = new String[R][C];
        dist1 = new int[R][C];
        dist2 = new int[R][C];
        for (int i = 0; i < R; i++) {
            st = new StringTokenizer(bf.readLine());
            String line = st.nextToken();
            for (int j = 0; j < C; j++) {
                maze[i][j] = String.valueOf(line.charAt(j));
                dist1[i][j] = -1;
                dist2[i][j] = -1;
                if(line.charAt(j) == 'F') {
                    fireQueue.add(new Node(i,j));
                    dist1[i][j] = 0;
                }
                if(line.charAt(j) == 'J') {
                    jQueue.add(new Node(i,j));
                    dist2[i][j] = 0;
                }
            }
        }

        while (!fireQueue.isEmpty()){
            Node curr = fireQueue.poll();
            for (int dir = 0; dir < 4; dir++) {
                int nx = curr.getX() + dx[dir];
                int ny = curr.getY() + dy[dir];

                if(nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
                if(dist1[nx][ny] > -1 || maze[nx][ny].equals("#")) continue;
                dist1[nx][ny] = dist1[curr.getX()][curr.getY()]+1;
                fireQueue.add(new Node(nx, ny));
            }
        }

        boolean isExit = false;
        while (!jQueue.isEmpty() && !isExit){
            Node curr = jQueue.poll();
            for (int dir = 0; dir < 4; dir++){
                int nx = curr.getX() + dx[dir];
                int ny = curr.getY() + dy[dir];

                if(nx < 0 || nx >= R || ny < 0 || ny >= C){
                    count = dist2[curr.getX()][curr.getY()]+1;
                    isExit = true;
                    break;
                }
                //이미 방문한 곳이거나 벽이면
                if(dist2[nx][ny] >= 0 || maze[nx][ny].equals("#") || maze[nx][ny].equals("F")) continue;
                //불전파 시간에 지훈이가 다음지나갈 곳에서 마주칠 수 있다면
                if(dist1[nx][ny] != -1 && dist1[nx][ny] <= dist2[curr.getX()][curr.getY()]+1) continue;

                dist2[nx][ny] = dist2[curr.getX()][curr.getY()]+1;
                jQueue.add(new Node(nx, ny));
            }
        }

        System.out.println(count == 0 ? "IMPOSSIBLE" : count);

    }

    public static class Node {
        private int x;
        private int y;
        
        public Node (int x, int y){
            this.x = x;
            this.y = y;
        }

        public int getY() {
            return y;
        }

        public int getX() {
            return x;
        }
    }
}