Pythonで目標を達成するための最短経路を見つけるためのプログラム

セルに「X」、「O」、「*」、「＃」などのさまざまな記号が含まれ、記号がさまざまな意味を持つグリッドが与えられたとします。

• 「＃」は到達したい目標セルです。
• 「O」は、ゴールセルに移動できる無料のセルです。
• 「*」はセル内の位置です。
• 「X」はブロックされたセルであり、それを介して移動することはできません。

グリッド内の現在の位置からゴールセルに到達するために必要な移動の数を見つける必要があります。目標に到達できない場合は、-1を返します。グリッドはプログラムへの入力として与えられます。

したがって、入力が次のような場合

その場合、出力は2になります

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

• m：=グリッドの行数
• n：=グリッドの列数
• 0からmの範囲のiについては、
  • 0からnの範囲のjについては、
    • grid [i、j]が "*"と同じ場合、
      • ループから抜け出す
    • それ以外の場合、
      • 次の反復に進む
    • ループから抜け出す
• ans：=0
• queue：=整数ペア（i、j）を含む新しいリスト
• grid [i、j]：="X"
• キューが空でないときに、実行します
  • ans：=ans + 1
  • newq：=新しいリスト
  • キュー内のi、jごとに、
    • 各iiについて、jj in（i-1、j）、（i、j-1）、（i、j + 1）、（i + 1、j）、do
      • 0 <=ii
      • grid [ii、jj]が "＃"と同じ場合、
        • 回答を返す
      • newqの最後にii、jjを挿入します
      • grid [ii、jj]：="X"
• queue：=newq

例

理解を深めるために、次の実装を見てみましょう-

def solve(grid):
   m, n = len(grid), len(grid[0])
   for i in range(m):
      for j in range(n):
         if grid[i][j] == "*": break
      else: continue
      break
   ans = 0
   queue = [(i, j)]
   grid[i][j] = "X"
   while queue:
      ans += 1
      newq = []
      for i, j in queue:
         for ii, jj in (i-1, j), (i, j-1), (i, j+1), (i+1, j):
            if 0 <= ii < m and 0 <= jj < n and grid[ii][jj] != "X":
               if grid[ii][jj] == "#": return ans
               newq.append((ii, jj))
               grid[ii][jj] = "X"
      queue = newq
   return -1

print(solve([['X', 'X', 'O', 'X'],['X', 'X', '*', 'X'],['X', '#',
'O', 'X'],['X', 'X', 'X', 'X']]))

入力

[['X', 'X', 'O', 'X'],
['X', 'X', '*', 'X'],
['X', '#', 'O', 'X'],
['X', 'X', 'X', 'X']]

出力

2