# BOJ - 5427 - 불

Updated:

``````import sys
from collections import deque

def BFS(fire, person, W, H, maps, visit):
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]

while person:
temp = deque()
while person:
x, y = person.popleft()
if maps[x][y] == "*":
continue

if x == 0 or x == H-1 or y == 0 or y == W-1:
if maps[x][y] != "*": return maps[x][y]

for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < H and 0 <= ny < W:
if maps[nx][ny] == "." and maps[nx][ny] != "*":
maps[nx][ny] = maps[x][y] + 1
temp.append((nx, ny))
person = temp

temp = deque()
while fire:
x, y = fire.popleft()

for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < H and 0 <= ny < W:
if visit[nx][ny] == False and maps[nx][ny] != "#":
maps[nx][ny] = "*"
visit[nx][ny] = True
temp.append((nx, ny))
fire = temp
return "IMPOSSIBLE"

def solution():
T = int(input())
for _ in range(T):
maps = []
fire = deque()
person = deque()
W, H = map(int, sys.stdin.readline().split())
visit = [[False] * W for _ in range(H)]
for _ in range(H):

for i in range(H):
for j in range(W):
if maps[i][j] == "@":
person.append((i, j))
maps[i][j] = 1
elif maps[i][j] == "*":
fire.append((i, j))
visit[i][j] = True
print(BFS(fire, person, W, H, maps, visit))

solution()
``````

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

Categories:

Updated: