불이 번져가는 경로와 지훈이가 탈출할 수 있는 경로 두 가지를 생각해야 한다.
2차원 배열에서 불이 번져가는 경로를 먼저 구하고 (bfs함수 호출), 그 다음 지훈이가 갈 수 있는 경로를 구한다.
불이 번져가는 경로는 벽이 아닐 경우 네 방향(상,하,좌,우)로 가능하고
지훈이는 벽이 아닐 경우 네 방향으로, 그리고 불이 없는 곳으로 이동이 가능하다.
지훈이가 불이 도달하기 전에 미로를 탈출 할 수 없는 경우 IMPOSSIBLE 을 출력한다.
시작점을 한번에 queue에 넣는다.
import java.util.*;
import java.io.*;
class Position{
int x;
int y;
Position(int x, int y) {
this.x = x;
this.y = y;
}
}
public class Main{
static int R, C;
static boolean[][] visited;
static char[][] maze;
static int[][] dist;
static int min = Integer.MAX_VALUE;
static int[][] fire;
static boolean flag = false;
static Queue<Position> queue = new LinkedList<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
maze = new char[R][C];
visited = new boolean[R][C];
dist = new int[R][C];
fire = new int[R][C];
for(int i=0; i<R; i++) {
String str = br.readLine();
for(int j=0; j<C; j++) {
maze[i][j] = str.charAt(j);
if(maze[i][j] == 'F') {
queue.add(new Position(i, j));
visited[i][j] = true;
}
}
}
bfsF();
//visited 방문여부 초기화
for(int i=0; i<R; i++) {
for(int j=0; j<C; j++) {
visited[i][j] = false;
}
}
//queue 초기화
queue = new LinkedList<>();
for(int i=0; i<R; i++) {
for(int j=0; j<C; j++) {
if(maze[i][j] == 'J') {
queue.add(new Position(i, j));
visited[i][j] = true;
}
}
}
bfsJ();
if(!flag)
System.out.println("IMPOSSIBLE");
else
System.out.println(min);
}
static void bfsF() {
int[] dx = {-1, 0, 1, 0};
int[] dy = {0, -1, 0, 1};
while(!queue.isEmpty()) {
Position out = queue.poll();
for(int i=0; i<4; i++) {
int nx = out.x + dx[i];
int ny = out.y + dy[i];
if(nx < 0 || ny < 0 || nx >= R || ny >= C) continue;
else if(visited[nx][ny] || maze[nx][ny] == '#' ) continue;
else {
queue.add(new Position(nx, ny));
visited[nx][ny] = true;
fire[nx][ny] = fire[out.x][out.y] + 1;
}
}
}
}
static void bfsJ() {
int[] dx = {-1, 0, 1, 0};
int[] dy = {0, -1, 0, 1};
while(!queue.isEmpty()) {
Position out = queue.poll();
for(int i=0; i<4; i++) {
int nx = out.x + dx[i];
int ny = out.y + dy[i];
if(nx < 0 || ny < 0 || nx >= R || ny >= C) {
flag = true;
min = dist[out.x][out.y] + 1;
return ;
}
else if(visited[nx][ny] || maze[nx][ny] == '#' || maze[nx][ny] == 'F') continue;
else if(fire[out.x][out.y] != 0 && dist[out.x][out.y]+1 >= fire[nx][ny]) continue;
else {
queue.add(new Position(nx, ny));
visited[nx][ny] = true;
dist[nx][ny] = dist[out.x][out.y] + 1;
}
}
}
}
}