220301-壁を破って移動

壁を壊して移動:白駿2206号

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を出力します.

I/O例
InputOutput6 4010011101000000001110000154 40111111111111110-1
のり付け
1.解説

ダイナミックプランニング法により解決できます.

の一般的なダイナミックプランニング法とは異なり、変数として「破壁」条件が付加されています.

(r,c,w):r(行)、c(列)、w

未破壁はwを0とする、破壁はwを1とする

とする.

BFSで最短距離を探す.

のような座標であっても,壁が破壊された場合と破壊されなかった場合とでは異なる座標であると考えられる.

2.プログラム

n,m,board入力

にアクセスし、答え

を初期化します.

インデックスを使用して初期座標(0,0,1,0):(r,c,cnt,w)

を設定します.

BFSアルゴリズムによる最短距離ナビゲーション

(r,c,cnt,w):行、列、移動数、壁移動

次座標値が0の場合、

を壁面呼吸の影響を受けないように移動する

次座標値が1の場合、wが0の場合のみ

移動する.

の最終座標に達するとcntを返し、-1に達しないと

を返す.

# 코드
from collections import deque

n, m = map(int, input().split(' '))
board = [list(map(int, input())) for _ in range(n) ]
visited = {}
answer = -1

points = deque([])
# 좌표 r(행), 좌표 c(열), 이동 수, 벽 이동
points.append((0, 0, 1, 0))
# 좌표 r(행), 좌표 c(열), 벽 이동
visited[(0, 0, 0)] = True

end_r, end_c = n-1, m-1
while points:
    r, c, cnt, wall = points.popleft()
    # 최종 좌표일 경우 값 반환 및 종료
    if r == end_r and c == end_c:
        answer = cnt
        break
    # 상, 하, 좌, 우 탐색
    for d_r, d_c in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        new_r, new_c = r + d_r, c + d_c

        # 범위를 넘억가는 경우 패스
        if new_r < 0 or new_r >=n or new_c <0 or new_c >= m:
            continue
        # 길인 경우 탐색
        if board[new_r][new_c] == 0 and (new_r, new_c, wall) not in visited:
            points.append((new_r, new_c, cnt+1, wall))
            visited[(new_r, new_c, wall)] = True
        # 벽인 경우 벽을 부수고 이동
        # 단, 벽을 이미 부순 경우는 이동할 수 없다.
        if board[new_r][new_c] == 1 and wall == 0:
            points.append((new_r, new_c, cnt+1, 1))
            visited[(new_r, new_c, 1)] = True

print(answer)

Input
6 4
0100
1110
1000
0000
0111
0000

Input
4 4
0111
1111
1111
1110