壁を破壊して移動

白駿2206号:壁を破って進む

アイデア

まず思いついた方法はすべての壁(1)を道(0)に変えてBFSを行い,壁の最大個数はNM個であるため時間的複雑度はO(N^2 M^2)であり,解くことができない.
すべての壁は破ることができないので、道を歩いて壁に出会ったとき、もしあなたが壁を破ることがなければ、あなたはそれを破ることができて、もしあなたがそれを破ったことがあるならば、あなたはそれを探求することができません.しかし、問題があります.私は壁を破って来たのか、それともこのように来たのか分からない.壁にぶつかった状態を記録してこそ解くことができる.
どうすれば壁を壊した状態を記録できますか?BFSを行う場合,キューに次のノードの情報を挿入するプロセスがある.同時に「壁を破って1、壁を破らずに0」の状態を提供します.
そして、「壁を破って来た場合のみ使用するグラフ」を別途作成して使用します.元の図形から壁を打ち砕くと、元の図形の壁を残し、壁を打ち砕いてから使用する図形の同じ位置の壁だけを打ち砕き、そこから探索を開始します.
では、壁を割るたびにグラフを作り直しますか?考えてもいいですが、もう一つ作って使うだけでいいです.
現在のノードに対して、上下左右4方向のノードから適切なノードを選択してキューに入れます.このとき1は壁なので、ナビゲートは行いません.(元の図形の位置を見てみましょう.壁を割った人もいるかもしれませんから)1ではなく、他の数字であれば、「現在のノードの中の数字」に比べて1でなければ(通ったばかりの長さであれば差は1であるはずです.数字を1つずつ加算して、どれだけの格を移動したかを記録していますので)探索します.つまり、再利用できるということです.
言葉で説明するのはちょっと難しいですが、注釈のコードを見ると分かりやすいかも・・・

from collections import deque

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
N, M = map(int, input().split())

graph = [[[] for _ in range(N)] for _ in range(2)]
for i in range(N):
    str = input()
    for c in str:
        for z in range(2):
            graph[z][i].append(int(c))

def bfs(graph):
    res = 987654321
    q = deque()
    q.append((0, 0, 0))
    graph[0][0][0] = 1
    while q:
        z, y, x = q.popleft()
        if y == N - 1 and x == M - 1:
            res = min(res, graph[z][y][x])
        # 벽을 부수고 온 경우
        if z == 1:
            for i in range(4):
                ny, nx = y + dy[i], x + dx[i]
                # 맵 밖으로 벗어났을 때
                if ny < 0 or nx < 0 or ny >= N or nx >= M:
                    continue
                # 벽 만났을 때 (원본 그래프로 체크)
                elif graph[0][ny][nx] == 1:
                    continue
                # 길 만났을 때
                elif graph[1][ny][nx] == 0:
                    graph[1][ny][nx] = graph[1][y][x] + 1
                    q.append((1, ny, nx))
                # 누가 지나온 길 만났을 때
                else:
                    # 내가 방금 밟은거 아니면
                    if graph[1][ny][nx] != graph[1][y][x] + 1:
                        graph[1][ny][nx] = graph[1][y][x] + 1


        else:
            for i in range(4):
                ny, nx = y + dy[i], x + dx[i]
                # 맵 밖으로 벗어났을 때
                if ny < 0 or nx < 0 or ny >= N or nx >= M:
                    continue
                # 벽 만났을 때 (원본 그래프로 체크)
                elif graph[0][ny][nx] == 1:
                    # 부순 적 없는 벽이면
                    if graph[1][ny][nx] == 1:
                        graph[1][ny][nx] = graph[0][y][x] + 1
                        q.append((1, ny, nx))
                # 길 만났을 때
                elif graph[0][ny][nx] == 0:
                    graph[0][ny][nx] = graph[0][y][x] + 1
                    q.append((0, ny, nx))
                # 지나온 길 만났을 때
                else:
                    continue
    return res


ans = bfs(graph)
if ans == 987654321:
    print(-1)
else:
    print(ans)

おしゃべり

まる3日間私を苦しめていた.グラフの問題をもっと解くべきだでは、奇抜な考えはどう思いますか.psが上手な人は羨ましいですね