Pythonで迷路脱出に必要なコンパスの使用回数が十分かどうかを判定するプログラム

問題の概要

迷路に閉じ込められ、出口を探して脱出を目指すゲームを想像してみてください。この迷路は n 行 m 列の行列として表現でき、各セルには「O」「D」「S」「-」のいずれかの記号が格納されています。

• O：塞がれた通路（壁）。通過できない
• D：迷路からの出口
• S：自分のスタート地点
• -：自由に移動できる通路

「-」のマークされたセルはどこでも自由に行き来できます。さらに、出口（「D」のセル）への道を見つけるためのコンパスも所持しています。進むべき方向を確認したい場面ではコンパスを使う必要がありますが、その使用回数は最大で k 回までです。

迷路を表す行列とコンパスの使用可能回数が与えられたとき、その回数以内で迷路から脱出できるかどうかを判定します。脱出可能であれば True を、不可能であれば False を返します。

入力例

n = 4、m = 11、k = 3 の場合、出力は True になります。

解法のアプローチ

この問題は、次の手順に従って解きます。

1. path_search() 関数を定義する

引数として curr_pos（現在位置）、grid（迷路）、total_rows（総行数）、total_cols（総列数）、k（残りのコンパス使用回数）、predecessor（直前の位置の記録）を受け取ります。

• x := curr_pos の x 座標
• y := curr_pos の y 座標
• grid[x][y] が「D」と等しい場合：
  • k が 0 であれば True を返す
  • それ以外は False を返す
• それ以外の場合：
  • parent := predecessor[curr_pos]
  • succ_pos := succesor_positions(curr_pos, grid, total_rows, total_cols, parent) の戻り値からなる新しいリスト
  • use_compass := succ_pos のサイズが 1 より大きければ True（＝複数の選択肢がある分岐点のためコンパスを使用）
  • succ_pos 内の各 position に対して以下を実行：
    • predecessor[position] := curr_pos
    • use_compass が真であれば、path_search(position, grid, total_rows, total_cols, k - 1, predecessor) を呼び出す
    • それ以外は、path_search(position, grid, total_rows, total_cols, k, predecessor) を呼び出す

2. succesor_positions() 関数を定義する

引数として curr_pos、grid、total_rows、total_cols、parent（親位置）を受け取ります。

• x := curr_pos の x 座標
• y := curr_pos の y 座標
• succ_pos := 新しい空リスト
• y > 0 の場合：left := (x, y - 1) を succ_pos の末尾に追加
• y < total_cols - 1 の場合：right := (x, y + 1) を末尾に追加
• x > 0 の場合：up := (x - 1, y) を末尾に追加
• x < total_rows - 1 の場合：down := (x + 1, y) を末尾に追加
• 最後に、移動先のセルが壁「O」ではなく、親位置とも異なるという条件を満たす要素だけをフィルタリングして返す

3. 全体の実行手順

• curr_pos := 新しい空のペア
• グリッド内の各行 row とインデックス i、さらに各行の各要素 element とインデックス j を走査し、element が「S」であれば curr_pos := (i, j) と設定する
• predecessor := 初期値として curr_pos := None を持つ新しいマップ（辞書）
• path_search(curr_pos, grid, n, m, k, predecessor) を実行する

ポイントは、コンパスが「分岐点」でのみ消費されるという点です。進める道が複数ある場所では方向の判断が必要になるため k を 1 減らし、道が一本しかない場合はコンパスなしで進めます。出口「D」に到達した時点で残り回数がちょうど 0 になっていれば、コンパスの使用回数は十分だったことになり True が出力されます。

ソースコード（Python）

理解を深めるために、以下の実装例を見てみましょう。

def path_search(curr_pos, grid, total_rows, total_cols, k, predecessor):
    x, y = curr_pos
    if grid[x][y] == "D":
        if k == 0:
            print('True')
        else:
            print('False')
    else:
        parent = predecessor[curr_pos]
        succ_pos = list(succesor_positions(curr_pos, grid, total_rows, total_cols, parent))
        use_compass = len(succ_pos) > 1
        for position in succ_pos:
            predecessor[position] = curr_pos
            if use_compass:
                path_search(position, grid, total_rows, total_cols, k - 1, predecessor)
            else:
                path_search(position, grid, total_rows, total_cols, k, predecessor)

def succesor_positions(curr_pos, grid, total_rows, total_cols, pred):
    x, y = curr_pos
    succ_pos = []
    if y > 0:
        left = (x, y - 1)
        succ_pos.append(left)
    if y < total_cols - 1:
        right = (x, y + 1)
        succ_pos.append(right)
    if x > 0:
        up = (x - 1, y)
        succ_pos.append(up)
    if x < total_rows - 1:
        down = (x + 1, y)
        succ_pos.append(down)
    return filter(lambda pos: grid[pos[0]][pos[1]] != "O" and pos != pred, succ_pos)

def solve(grid, n, m, k):
    curr_pos = ()
    for i, row in enumerate(grid):
        for j, element in enumerate(row):
            if element == 'S':
                curr_pos = (i, j)
    path_search(curr_pos, grid, n, m, k, predecessor = {curr_pos: None})

grid = [['-', 'O', '-', 'O', '-', '-', '-', '-', '-', '-', 'O'],
['-', 'O', 'D', '-', 'O', '-', 'O', 'O', 'O', '-', 'O'],
['-', 'O', 'O', '-', 'O', '-', 'O', 'S', '-', '-', '-'],
['-', '-', '-', '-', '-', '-', 'O', 'O', 'O', 'O', '-']]

solve(grid, 4, 11, 3)

入力

grid = [['-', 'O', '-', 'O', '-', '-', '-', '-', '-', '-', 'O'],
['-', 'O', 'D', '-', 'O', '-', 'O', 'O', 'O', '-', 'O'],
['-', 'O', 'O', '-', 'O', '-', 'O', 'S', '-', '-', '-'],
['-', '-', '-', '-', '-', '-', 'O', 'O', 'O', 'O', '-']] , 4, 11, 3

出力

True