문제

상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다.

매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.

빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하는 프로그램을 작성하시오.

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

from collections import deque

# 1. 불 확산
# 2. 상구 이동


def bfs():
    global start, fire, w, h, arr
    queue = deque()
    for x, y in fire:
        queue.append((x, y, arr[x][y]))
    x, y = start
    queue.append((x, y, arr[x][y]))
    time = 10**9
    
    while queue:
        x, y, what = queue.popleft()
        
        if what != "*" and (x == 0 or y == 0 or x == h-1 or y == w-1):
            time = min(time, what+1)
            continue
        
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if nx < 0 or ny < 0 or nx >= h or ny >= w:
                continue
            if arr[nx][ny] == "#" or arr[nx][ny] == "*":
                continue
            if what == "*":
                arr[nx][ny] = "*"
                queue.append((nx, ny, arr[nx][ny]))
            else:
                if arr[nx][ny] == -1 or what + 1 < arr[nx][ny]:
                    arr[nx][ny] = what + 1
                    queue.append((nx, ny, arr[nx][ny]))
                    
    return time


t = int(input())
for _ in range(t):

    w, h = map(int, input().split())
    arr = [list(map(str, input())) for _ in range(h)]

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

    start, fire = [], []
    for x in range(h):
        for y in range(w):
            if arr[x][y] == "@":
                start = (x, y)
                arr[x][y] = 0
            elif arr[x][y] == "*":
                fire.append((x, y))
            elif arr[x][y] == ".":
                arr[x][y] = -1


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

백준 5427 불