[伯俊]4179火!

質問する

入力

しゅつりょく

コミットコード

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

r, c = map(int, input().split())
table = [list(input().rstrip()) for _ in range(r)]
visited = [[False] * c for _ in range(r)]

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
jx, jy= 0, 0 # J는 입력에서 하나만 주어진다.
fire = [] # 

def bfs():
  
    qq = deque()
    # movements, x, y
    qq.append([0, jx, jy])
    visited[jx][jy] = True

    ffq = deque()
    for fx, fy in fire:
        # x, y
        ffq.append([fx, fy]) 
  
    while qq:
        fq = ffq
        q = qq
        ffq = deque()
        qq = deque()

	# 불 먼저 이동 (불의 위치를 넣어놓은 fq queue)
        while fq:
            _fx, _fy = fq.popleft()
           
            for i in range(4):
                ffx = _fx + dx[i]
                ffy = _fy + dy[i]

                if ffx < 0 or ffy < 0 or ffx >= r or ffy >= c: continue
                # 불은 벽을 지나갈 수 없고, 이미 불이 난 곳을 또 지나갈 필요가 없다.
                if table[ffx][ffy] == '#' or table[ffx][ffy] == 'F': continue
                table[ffx][ffy] = 'F' # 불은 이동하면 배열에 표시한다.
                ffq.append([ffx, ffy]) # 다른 queue에 이동한 불의 위치를 저장한다.
        # 지훈이 이동
        while q:
            movements, _x, _y = q.popleft()

	    # 지훈이가 가장자리에 도착했으므로 탈출 성공 (아예 가장자리 밖으로 나가야 탈출이기 때문에 이동횟수 + 1 을 해준다.
            if _x == 0 or _y == 0 or _x == r - 1 or _y == c - 1:   >   
                return movements + 1
              
            for i in range(4):
                x = _x + dx[i]
                y = _y + dy[i]

                if x < 0 or y < 0 or x >= r or y >= c: continue
                # 벽인 곳도 가장자리인 곳으로도 이동할 수 없다.
                if table[x][y] == '#' or table[x][y] == 'F': continue
                if visited[x][y]: continue
                visited[x][y] = True # '7% 틀렸습니다' 원인, 지훈이 방문체크 안하면 7%
                qq.append([movements + 1, x, y])

    return "IMPOSSIBLE"

for i in range(r):
    for j in range(c):
        if table[i][j] == 'J':
            jx, jy = i, j
            table[i][j] = '.'
        if table[i][j] == 'F':
            fire.append([i, j])

print(bfs())