[Algorithm] BaekJoon : 2206. Pythonによる壁の破壊と移動

[問題のショートカット]https://www.acmicpc.net/problem/2206

📌問題の説明

N×Mのマトリックス表現のマッピングがあります.地図では、0は移動可能な位置、1は移動不可能な壁の位置を示す.(1,1)から(N,M)の位置に移動し、最短経路に移動します.最短パスとは、地図上の最小セルを通るパスで、開始セルと終了セルが含まれます.
移動中に壁を割ったり移動したりする経路がもっと短い場合は、壁を割って移動することができます.
1つのセルで移動できるセルは上下左右に隣接するセルです.
地図を指定すると、最短パスを解くプログラムが作成されます.
入力
第1行はN(1≦N≦1000),M(1≦M≦1000)を与える.次のN行はMの数字で地図を与えます.(1,1)と(N,M)は常に0であると仮定する.
しゅつりょく
1行目に最短距離を出力します.不可能な場合は-1を出力します.

💡 問題を解く

人の解答を見てもわかりにくい問題.
最短距離を見つけるためにBFSを使うことは理解したが、問題の核心である「壁を壊すことができる」という正確な表現はなかった.
問題を解決するには、アクセスするかどうかを示す配列を既存の配列とは異なり、3 Dで表す必要があります.
対応する座標の移動距離(Move Distance)が入力されている場合は、3 D配列で壁を破るときの最短距離(Short Distance on on Wall)と壁を破らないときの最短距離(Short Distance on Wall None Wall)をそれぞれ検索します.

アクセス[r][c][0]:破壁時(r,c)の最短距離

アクセス[r][c][1]:最短距離

(r,c)壁を破る必要はありません
また、参照するセルの行と列の座標もキューに含まれている場合は、壁が破られたかどうかを判断する値(0または1)を挿入する必要があります.
コードは次のとおりです.

import sys
from collections import deque

d = [(-1, 0), (1, 0), (0, 1), (0, -1)]

def bfs():
    visited = [[[0] * 2 for _ in range(M)] for _ in range(N)]
    queue = deque([(0, 0, 1)])
    visited[0][0][1] = 1
    while queue:
        r, c, used = queue.popleft()
        if r == N-1 and c == M-1:
            return visited[r][c][used]
        for idx in range(4):
            nr = r + d[idx][0]
            nc = c + d[idx][1]
            if 0 <= nr < N and 0 <= nc < M: 
                if matrix[nr][nc] == 1 and used == 1: # 벽이고 아직 뚫지 않았다면
                    visited[nr][nc][0] = visited[r][c][1] + 1 # visited[nr][nc][0] 값 최신화
                    queue.append((nr, nc, 0))
                elif matrix[nr][nc] == 0 and visited[nr][nc][used] == 0: # 이동 가능한 칸이며 아직 지나가지 않았다면
                    visited[nr][nc][used] = visited[r][c][used] + 1 # used 값에 따라 visited[nr][nc][used] 값 최신화
                    queue.append((nr, nc, used))
    return -1

N, M = map(int, input().split())
matrix = [list(map(int, ''.join(sys.stdin.readline().rstrip()))) for _ in range(N)]
print(bfs())