[伯俊]4179火!

火~火~!

質問する

志訓は迷宮で働いている.智勲を助けて迷宮を脱出せよ!
智勲の迷路での位置と点火された位置を考慮して、智勲が火に焼かれる前に脱出できるかどうか、そしてどれだけ速いスピードで脱出できるかを決めなければならない.
智勲と火は毎分水平または垂直に1格移動する(傾斜せずに移動する).
火は各点から4方向に拡散する.
ジフンは迷宮の端に近い空間から脱出できる.
智勲と火は壁のある空間を通ることができない.

入力

入力された最初の行には、スペースで区切られた2つの整数RとCが与えられます.ただし,1≦R,C≦1000であった.Rは迷宮行の個数,Cは列の個数である.
次の入力では、R行にそれぞれ迷路行が与えられる.
各文字の意味は次のとおりです.

#:壁

.: 通過可能空間

J:ジフンの迷宮での初期位置(通過可能な空間)

F:発火空間

Jは入力に1つだけ与えられる.

しゅつりょく

智勲が火が到着するまで迷宮を脱出できなければ、IMPOSIBLEを出力する.
智勲が迷宮から脱出できれば、最も速い脱出時間を出力する.

コミットコード

7%間違っています:智勲は訪問を確認しましたか?

21%エラー:実装に問題があります.

智勲と火は毎分水平または垂直に1格移動する.
以上の条件を満たすと,21パーセントの誤りを逃れることができる.

ドルを智勲より先に移動させた.(まずは火の移動かジフンの移動か…)

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())