[BOJ]破壁移動(no.206)

20930 ワード
BFS algorithm python boj テキストリンク
質問する
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問題と同じです.

  • どんな壁を破壊して最短経路を変えるのか...壊していない方が早い場合もあります.

  • すべての壁をパラメータとしてbfsを迂回すべきではないでしょうか.答えは出てくるけど、歳月よ、君の月牙の果てに出てくる答えは意味がない.

  • 破壊壁のパスをグラフィックを構成するブランチとして作成したらどうなりますか?

  • では、壁に出会うたびに、まず割って、それから一度壁を割った事実を覚え続けて、外に出ればいいのではないでしょうか.(ブランチの概念をもう1つ作成)

  • すべての壁が一度作られます

  • bfsだから先に着いた人はきっと最短経路ええ、いいですか.これでいいみたい??
    • そこで、下ののりで、3トンくらいのところに松露を作りました.
    📌 説明する
    import sys
input = sys.stdin.readline
print = sys.stdout.write

def main():
    n, m = map(int, input().split())
    grid = tuple(tuple(map(int, input().rstrip())) for _ in range(n))
    dx, dy = [1,-1,0,0], [0,0,1,-1]

    def bfs():
        visited = [[[False]*m for _ in range(n)] for _ in range(2)]
        q = [(0,0,False)]
        visited[0][0][0] = True
        dist = 1

        while q:
            tmp = []
            for x,y,broken in q:
                if x == n-1 and y == m-1: return dist
                
                for i in range(4):
                    nx, ny = x+dx[i], y+dy[i]

                    if 0 <= nx <n and 0 <= ny <m:
                        if grid[nx][ny] == 1 and not broken:
                            visited[0][nx][ny] = True
                            tmp.append((nx,ny,True))
                        elif grid[nx][ny] == 0 and not visited[broken][nx][ny]:
                            visited[broken][nx][ny] = True
                            tmp.append((nx,ny,broken))
            
            q = tmp
            dist += 1
        return -1

    print("%d" % bfs())

if __name__ == "__main__":
    sys.exit(main())

  • ほどけたけどメモリを食べすぎたような気がする.

  • いくつかのグリディを反映しています.(壁が破れていない場合は、最初にアクセスします.そうでない場合は開きません)

  • アクセスリストも単純にアクセスを表示しているだけなので太ってしまいました.true/falseにアクセスするのではなく、壁を破壊するかどうかを値として保存することで、リスト次元を減らします.(もちろん、初期化状態は、アクセスするかどうかを判断するために個別の値で区別する必要があります.)
    • に注意
    上記のグリンディは、優先度が明確な場合にのみ適用されるべきである.
    そこで,改良後の解答を以下に示す.
    📌 最終的なソリューション
    import sys
input = sys.stdin.readline

def main():
    n, m = map(int, input().split())
    grid = tuple(input().rstrip() for _ in range(n))
    dx, dy = [1,-1,0,0], [0,0,1,-1]

    def bfs():
        cache = [[2]*m for _ in range(n)] # 0-벽안뚫음, 1-벽뚫음, 2-초기화(미방문 상태)
        q = [(0,0,0)]
        cache[0][0] = 0
        dist = 1

        while q:
            tmp = []
            for x,y,chance in q:

                if x == n-1 and y == m-1: return dist
                for i in range(4):
                    nx, ny = x+dx[i], y+dy[i]

                    if 0 <= nx <n and 0 <= ny <m:
                        if cache[nx][ny] > chance:
                            if grid[nx][ny] == '1' and chance != 1:
                                cache[nx][ny] = 1
                                tmp.append((nx,ny,1))
                            elif grid[nx][ny] == '0':
                                cache[nx][ny] = chance
                                tmp.append((nx,ny,chance))
            
            q = tmp
            dist += 1
        return -1

    print(bfs())

if __name__ == "__main__":
    sys.exit(main())
    レビュー
  • 図ノードは地図情報しか含まれないという偏見を捨てましょう.特殊条件により分岐してもよい.
    • UISegmentedControl
    ASP.NET MVCデータ削除