문제

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

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

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

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

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

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

# 4179
import sys
input = lambda: sys.stdin.readline().strip()

from collections import deque

# bfs를 이용 -> 지훈 > 불 순서로 이동

r, c = map(int, input().split())
arr = [list(map(str, input())) for _ in range(r)]
start, fire = 0, []

dx, dy = [-1, 0, 1, 0], [0, 1, 0, -1]

for x in range(r):
    for y in range(c):
        if arr[x][y] == "J":
            start = (x, y)
            arr[x][y] = 0
        elif arr[x][y] == "F":
            fire.append((x, y))
        elif arr[x][y] == ".":
            arr[x][y] = -1
            
def bfs():
    global r, c, arr, start, fire
    queue = deque()
    queue.append(start)
    for x, y in fire:
        queue.append((x, y))
    min_time = 10**9
        
    while queue:
        x, y = queue.popleft()
        
        if x == 0 or y == 0 or x == r-1 or y == c-1:
            if arr[x][y] != "F":
                min_time = min(min_time, arr[x][y] + 1)
                continue
                
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if nx < 0 or ny < 0 or nx >= r or ny >= c:
                continue
            if arr[nx][ny] == "#" or arr[nx][ny] == "F":
                continue
                
            if arr[x][y] == "F":
                arr[nx][ny] = "F"
                queue.append((nx, ny))
            else:
                if arr[nx][ny] == -1 or arr[x][y] + 1 < arr[nx][ny]:
                    arr[nx][ny] = arr[x][y] + 1
                    queue.append((nx, ny))

    return min_time    
                    
time = bfs()
if time == 10**9:
    print("IMPOSSIBLE")
else:
    print(time)

백준 4179 불!