Rat in a Maze
ネズミは n × n の maze の左上のマスからスタートします。ここで、1 は通行可能なマス、0 は壁を表し、右下のマスに到達しなければなりません。各移動では、通行可能なマスへ下（D）、左（L）、右（R）、または上（U）に1マス進みます。経路は同じマスを2回訪れることはなく、出口で終わります。
すべての経路を移動を表す文字列としてアルファベット順に返してください。経路がない場合は空の配列を返してください。
関数
- mazeinteger-2d-array
- n × n のグリッド。通行可能なセルは 1、壁は 0
- 戻り値string-array
- 左上から右下までのすべての経路を、移動の文字列としてアルファベット順に
制約
2 ≤ n ≤ 5maze[i][j]は0または1です。- すべてのテスト用迷路の経路数は最大2,000です。開いた5 × 5の迷路には8,512通りの経路があるため、テストには含まれていません。
例
- 入力
- maze = [[1, 1, 0, 0], [0, 1, 1, 0], [1, 1, 1, 0], [1, 0, 1, 1]]
- 出力
- ["RDDRDR", "RDRDDR"]
- 説明
- 最初は右側のセルだけが開いており、そこからは下のセルだけが開いているため、どちらの経路も
RDから始まります。3手目のDがRより前に来るため、RDDRDRが先に並びます。
- 入力
- maze = [[1, 1, 1], [1, 0, 1], [1, 1, 0]]
- 出力
- []
- 説明
- 出口である右下のセルは壁なので、そこを終点とする経路は存在せず、答えは空になります。ただし、それ以外のすべてのセルは通行可能です。
発展問題
4つすべての移動が許される場合、列挙せずに経路の数を数えられますか？数が手に負えなくなる前に、n はどこまで大きくできますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
経路とは開始セルからの移動の連続なので、一度に1つずつ移動を加えて作っていきます。各セルからの移動は最大4つです。許可されているのはどれでしょうか？
再帰関数を使って前進し、そのセルを離れる前に現在のセルを使用済みとしてマークしてください。そうすれば、経路がそのセルに戻ることはできません。呼び出しから戻ったら、マークを外してください。別の経路がそのセルを通る可能性があります。
アルファベット順に、
D、L、R、Uの順で手を試します。2つの経路は分岐した手で初めて異なり、文字の小さい方の分岐が先に探索されるため、経路はすでにソートされた状態で得られます。
解説
重複も抜けもなく、すべての経路を列挙する必要があります。バックトラッキングを使えば実現できます。経路を一度に1手ずつ延ばし、通ったマスを通行不可にし、そのマスから戻るときに通行可能に戻します。移動をアルファベット順に試すと、経路をソートされた順に並べられます。
すべての経路を幅優先で伸ばしてから、並べ替える
考え方
部分経路をキューに入れておきます。それぞれの経路には、現在のセル、訪問済みのセル、移動手順が含まれます。キューから1つ取り出し、開いていて未訪問のセルへの1手分の延長をすべてキューに追加します。出口に到達した経路は保存します。すべての経路がちょうど1回ずつ見つかります。セルが最大25個なら、訪問済みセルの集合は1つの整数に収まります。ビット r * n + c はセル (r, c) を表します。
キューは経路を短い順に取り出しますが、これはソート順ではありません。開いた5 × 5の迷路では、16手の DDDDRRRULLURRRDD が8手の DDDRDRRR より先にソートされます。そのため最後にソートしますが、キューには部分経路の層全体がメモリ上に保持されます。
アルゴリズム
- 開始地点または出口が壁の場合は、空の配列を返します。
- 開始地点をキューに追加します。セルは
(0, 0)、使用済み集合にはビット 0 を設定し、移動はありません。 - 次のエントリーを取り出します。出口にいる場合は、その移動経路を保存して続行します。
- そうでない場合、迷路内の通行可能で未使用のセルに移動する各手について、そのセル、セルのビットを追加した使用済み集合、および移動を末尾に追加した経路を持つエントリーを追加します。
- キューが空になったら、保存した経路をソートして返します。
from collections import deque
def findPaths(maze):
n = len(maze)
if maze[0][0] == 0 or maze[n - 1][n - 1] == 0:
return []
moves = (("D", 1, 0), ("L", 0, -1), ("R", 0, 1), ("U", -1, 0))
result = []
# Each entry is a path in progress: its cell, the cells it has used
# (bit r * n + c), and its moves so far.
queue = deque([(0, 0, 1, "")])
while queue:
r, c, used, path = queue.popleft()
if r == n - 1 and c == n - 1:
result.append(path)
continue
for letter, dr, dc in moves:
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < n and maze[nr][nc] == 1:
bit = 1 << (nr * n + nc)
if not used & bit:
queue.append((nr, nc, used | bit, path + letter))
result.sort() # shorter paths were found first, so sort by text
return resultアルファベット順でのバックトラッキング
考え方
再帰関数はセル上に立ちます。出口では移動経路を保存します。それ以外の場合は、経路が戻ってこられないようにセルを0に設定し、通行可能なセルへの各移動を試してから、後続の経路が通過できるようにセルを1に戻します。メモリ使用量は現在の経路分で、再帰の深さは最大でもn²です。
2つの経路は、異なる最初の移動まで同じ移動を共有し、その地点で探索は文字の小さい方の分岐を先に完了します。また、経路は出口で停止するため、ある経路が別の経路の始まりになることはありません。移動をD、L、R、Uの順に試すので、経路はソート順に保存されます。
アルゴリズム
- 開始地点または出口が壁の場合は、空の配列を返します。
backtrack(r, c)を記述します。(r, c)が出口の場合は、現在の移動経路を保存して戻ります。maze[r][c]を0に設定します。- 迷路内の通行可能なマスに移動できる手順
D、L、R、Uのそれぞれについて、その文字を追加し、再帰呼び出しを行ってから、その文字を削除します。 maze[r][c]を1に戻します。backtrack(0, 0)を呼び出し、保存した経路を返します。
def findPaths(maze):
n = len(maze)
result = []
if maze[0][0] == 0 or maze[n - 1][n - 1] == 0:
return result
# The moves in alphabetical order, so the paths come out sorted.
moves = (("D", 1, 0), ("L", 0, -1), ("R", 0, 1), ("U", -1, 0))
path = []
def backtrack(r, c):
if r == n - 1 and c == n - 1:
result.append("".join(path))
return
maze[r][c] = 0 # block the cell while this path uses it
for letter, dr, dc in moves:
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < n and maze[nr][nc] == 1:
path.append(letter)
backtrack(nr, nc)
path.pop()
maze[r][c] = 1 # open it again for the other paths
backtrack(0, 0)
return result
落とし穴と境界ケース
- 戻るときにセルの印を消し忘れること。セルがブロックされたままになり、後続の分岐がそこを通れなくなります。
DDRRとDDRURDを返す開いた3 × 3の迷路では、12通りの経路のうち2通りです。 - スタート地点や出口が壁の場合があることを忘れること。2つ目の例のように出口が壁の場合、出口の隣で終わる経路ではなく、空の答えを返さなければなりません。
- 下、上、左、右の順に移動を試すこと。経路の集合は正しいですが、順序が違います。アルファベット順は
D、L、R、Uです。
よくある質問3
Rat in a Maze の時間計算量はどれくらいですか？
最初の移動の後、経路は各セルで最大3つの選択肢があり、訪れるセル数は最大でも n² です。そのため、部分経路は O(3^(n²)) 個あり、それぞれを書き出すのに O(n²) かかります。壁や使用済みのセルによって、これは大幅に減ります。
バックトラックするとき、なぜ訪問済みマークを取り除かなければならないのでしょうか？
印は「以前に見た」ではなく、「現在の経路上にある」という意味でなければなりません。異なる2つの経路が同じセルを通ることがあります。探索がそのセルから戻った後も印が残っていると、そのセルを通る後続の経路はすべて見つからなくなります。
ネズミが右と下にしか移動できないとしたらどうでしょうか？
この場合、どの経路もセルに再び訪れることはないため、訪問済みの印を付ける必要はなく、すべての経路の移動回数はちょうど 2n-2 です。経路の数え上げは動的計画法になります。あるセルに到達する方法の数は、その上にある通行可能なセルに到達する方法の数と、左にある通行可能なセルに到達する方法の数の合計です。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def findPaths(maze):
# ここにコードを書いてくださいテスト #1
テスト #2
引数
maze = [[1, 1, 0, 0], [0, 1, 1, 0], [1, 1, 1, 0], [1, 0, 1, 1]]
期待される出力
["RDDRDR", "RDRDDR"]