[4179] 불

https://www.acmicpc.net/problem/4179

4179번: 불!

문제

지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!

미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다.

지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다)  이동한다. 

불은 각 지점에서 네 방향으로 확산된다. 

지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다. 

지훈이와 불은 벽이 있는 공간은 통과하지 못한다.

입력

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

다음 입력으로 R줄동안 각각의 미로 행이 주어진다.

 각각의 문자들은 다음을 뜻한다.

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

J는 입력에서 하나만 주어진다.

출력

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

지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다. 

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	static int M, N, Answer;
	static char[][] MAP;
	static Queue<POINT> jq = new LinkedList<>();
	static Queue<POINT> fq = new LinkedList<>();
	static boolean[][] jVisited;
	static boolean[][] fVisited;
	static int[] dx = {-1,1,0,0};
	static int[] dy = {0,0,-1,1};

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		M = sc.nextInt();
		N = sc.nextInt();

		MAP = new char[M][N];		
		jVisited = new boolean[M][N];
		fVisited = new boolean[M][N];

		for (int i = 0; i < M; i++) {
			String str = sc.next();
			MAP[i] = str.toCharArray();
		}
		// printMAP();
		boolean tf = bfs();
		
		if(tf)
			System.out.println(Answer+1);
		else
			System.out.println("IMPOSSIBLE");
	}

	private static boolean bfs() {
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				if (MAP[i][j] == 'J') {
					jq.offer(new POINT(i, j));
					jVisited[i][j] = true;
				}
				if (MAP[i][j] == 'F') {
					fq.offer(new POINT(i,j));
					fVisited[i][j] = true;
				}
			}
		}
		
		while(!jq.isEmpty()) {
			int jsize = jq.size();
			int fsize = fq.size();
			
			
			//불시작
			for(int i=0; i<fsize; i++) {
				POINT fp = fq.poll();			
				for(int j=0; j<4; j++) {
					int nextX = fp.x + dx[j];
					int nextY = fp.y + dy[j];
					
					if(nextX<0 || nextY<0||nextX>=M||nextY>=N) {
						continue;
					}
						
					if(MAP[nextX][nextY]=='#')
						continue;
					if(fVisited[nextX][nextY])
						continue;
					
					fVisited[nextX][nextY] = true;
					MAP[nextX][nextY] = 'F';
					fq.offer(new POINT(nextX,nextY));
				}
			}
			
			//System.out.println("불맵");
			//printMAP();
			
			//지훈시작
			for(int i =0; i<jsize;i++) {
				POINT jp = jq.poll();
				for(int j=0; j<4; j++) {
					int nextX = jp.x + dx[j];
					int nextY = jp.y + dy[j];
					
					if(nextX<0 || nextY<0||nextX>=M||nextY>=N) {					
						return true;						
					}					
					if(MAP[nextX][nextY]!='.')
						continue;
					if(jVisited[nextX][nextY])
						continue;
					
					jVisited[nextX][nextY]=true;
					MAP[nextX][nextY] = 'J';
					
					jq.offer(new POINT(nextX,nextY));
				}
			}
			Answer++;
			//System.out.println("지훈맵");
			//printMAP();
		}
		return false;
	}

	private static void printMAP() {
		for (int i = 0; i < M; i++) {
			System.out.println();
			for (int j = 0; j < N; j++) {
				System.out.print(MAP[i][j]);
			}
		}
	}
}


class POINT{
	int x;
	int y;
	
	POINT(int x, int y){
		this.x = x;
		this.y = y;
	}
}