[acmicpc] 5427. 불(python)

import sys
from collections import deque
input=sys.stdin.readline

dirs=[(1,0),(0,1),(-1,0),(0,-1)]
N=int(input())
def bfs():
    count=0
    while True:
        count+=1
        for j in range(len(fire)):
            r,c=fire.popleft()
            for i in range(4):
                nr,nc=r+dirs[i][0],c+dirs[i][1]
                if 0>nr or nr>=h or nc<0 or nc>=w:
                    continue
                if building[nr][nc]!='#' and building[nr][nc]!='*':
                    building[nr][nc]='*'
                    fire.append([nr,nc])
        for j in range(len(sang)):
            sr, sc = sang.popleft()
            for i in range(4):
                nr,nc=sr+dirs[i][0],sc+dirs[i][1]
                if 0>nr or nr>=h or nc<0 or nc>=w:
                    return count
                if building[nr][nc]=='.':
                    building[nr][nc]='@'
                    sang.append([nr,nc])
        if len(sang)==0: return "IMPOSSIBLE"
for _ in range(N):
    fire=deque()
    sang=deque()
    w, h = map(int, input().split())
    building=[list(input().strip()) for _ in range(h)]
    for r in range(h):
        for c in range(w):
            if building[r][c]=='@':
                sang.append([r,c])
            elif building[r][c]=='*':
                fire.append([r,c])
    print(bfs())

---

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

5427번: 불