[Baekjoon] 2206. 破壁移動[G 4]

📚 質問する

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

📖 に答える

これは最短経路でBFSで実現される.
アクセスを3 Dとしてマークします.2 D位置に[移動距離、ステータス]を追加します.
ステータスは:2、破壁アクセス:1、未破壁アクセス:0です.
移動距離は最大移動距離よりも大きく、約n*mに初期化される.
ステータスはアクセスされていないため、2に初期化されます.

インクリメンタルナビゲーションで壁に遭遇した場合、現在の破壊回数が0の場合にのみ壁に移動できます.このとき、破壊回数を1に増やします.
破壊回数が1の場合は移動しません.

壁にぶつからなければ、二つの状況を考えることができます.

破壊回数が同じまたは大きい場合
BFSナビゲーションでは,割り込み回数が同じであれば,最短距離ではないためナビゲーションは行われない.

移動位置の破壊回数が多い
破壊の回数がもっと少ないので、もう一度探求すべきだ.
初めて探索した場所が2なので破壊回数が0、1なら更新しますが、
破壊回数が1の場合、0で試してみることができます.

ループ文の過程でn-1,m-1インデックスの状態が2でない場合、値を入力するとループ文が終了して出力されます.
繰り返し文が終了すると、n-1、m-1インデックスの状態が2の場合、-1が出力されます.

📒 コード#コード#

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

n, m = map(int, input().split())
arr = [list(map(int, input().rstrip())) for _ in range(n)]
INF = n * m
dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]
visited = [[[INF, 2] for _ in range(m)] for _ in range(n)]
queue = deque()
queue.append((0, 0))
visited[0][0] = [1, 0]

while queue and visited[n-1][m-1][1] == 2:
    y, x = queue.popleft()
    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]
        if not(0 <= ny < n and 0 <= nx < m):
            continue
        if arr[ny][nx] == 0 and visited[y][x][1] < visited[ny][nx][1]:
                visited[ny][nx] = [visited[y][x][0] + 1, visited[y][x][1]]
                queue.append((ny, nx))
        else:
            if visited[y][x][1] == 0 and visited[ny][nx][1] == 2:
                visited[ny][nx] = [visited[y][x][0] + 1, 1]
                queue.append((ny, nx))

if visited[n-1][m-1][1] == 2:
    print(-1)
else:
    print(visited[n-1][m-1][0])

🔍 結果