Pythonで迷路から抜け出すためのコンパスの使用回数が十分かどうかを確認するプログラム

迷路に閉じ込められたゲームをプレイしているとします。私たちは迷路から抜け出す方法を見つけなければなりません。迷路は、x m行列として表すことができます。ここで、nは行の数、mは列の数です。マトリックスの各セル/要素には、記号「O」、「D」、「S」、または「-」のいずれかが含まれます。 「O」はパスがブロックされていることを意味し、「D」は迷路から抜け出す方法、「S」は開始位置、「-」はパスを移動できることを意味します。 '-'マークの付いたセルを自由に移動できます。これで、迷路からの出口パス（「D」セル）を見つけることができるコンパスもあります。方向を見つける必要があるときは、コンパスを使用する必要があります。ただし、コンパスは最大k回使用できます。迷路を行列として、コンパスを使用できる回数を考えると、コンパスを何度も使っただけで迷路から抜け出せるかどうかを調べなければなりません。可能であればTrueを返し、そうでない場合はFalseを返します。

したがって、入力がグリッド=

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

これを解決するには、次の手順に従います-

• 関数path_search（）を定義します。これには、curr_pos、grid、total_rows、total_cols、k、predecessorが必要です

  • x：=curr_posのx値

  • y：=curr_posのy値

  • grid [x、y]が "*"と同じ場合、

    • kが0と同じ場合、

      • Trueを返す

    • それ以外の場合

      • Falseを返す

    • それ以外の場合

      • 親：=先行[curr_pos]

      • succ_pos：=succesor_positions（curr_pos、grid、total_rows、total_cols、parent）の戻り値からの新しいリスト

      • use_compass：=succ_posのサイズが1より大きい場合はTrue

      • succ_posの位置ごとに、実行します

        • 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）

• 関数succesor_positions（）を定義します。これには、curr_pos、grid、total_rows、total_cols、parent

  が必要です。

  • x：=curr_posのx値

  • y：=curr_posのy値

  • succ_pos：=新しいリスト

  • o y> 0の場合、

    • 左：=x、y-1

    • succ_posの最後に左を挿入

  • y

    • 右：=x、y + 1

    • succ_posの最後に挿入

  • x> 0の場合、

    • up：=x-1、y

    • succ_posの最後に挿入

  • x

    • ダウン：=x + 1、y

    • succ_posの最後に挿入します

  • succ_posのすべての位置について、grid [position [0]、pos[1]]が

    の場合

  • 「X」と同じではなく、posが親と同じではない場合、-

    • 条件を満たすsucc_posの要素を返します

次に、次の操作を実行します-

• curr_pos：=新しい空のペア

• インデックスiごとに、グリッド内のアイテム行を実行します

  • インデックスjごとに、行のアイテム要素を実行します

    • 要素が「M」と同じ場合、

      • curr_pos：=i、jを含む新しいペア

• 前任者：=curr_pos：=最初はNullである新しいマップ

• path_search（curr_pos、grid、n、m、k、predecessor）

ソースコード（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