Pythonですべての木を燃やすのにかかる日数を見つけるためのプログラム

3つのタイプのセルがあるフォレストを表す2Dマトリックスがあるとします。0空のセル1ツリーセル2火のセルのツリー毎日、隣接するセル（上、下、左、右、対角線）木が燃えています。すべての木が燃えるのにかかる日数を見つけなければなりません。それが不可能な場合は-1を返します。

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

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

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

• ans：=0
• twos：=新しいリスト
• 行列の行数が0から行数の範囲のiについては、
  • 0から行列の列数までの範囲のjの場合、do
    • matrix [i、j]が2と同じ場合、
      • 2つの最後にペア（i、j）を挿入します
    • 2つが空ではない場合は、
      • temp：=新しいリスト
      • 2つのペア（i、j）ごとに、
        • [（i + 1、j）、（i、j + 1）、（i-1、j）、（i、j-1）]の各ペア（x、y）について、do
          • xとyが行列の範囲内にあり、matrix [x、y]が1の場合、
            • 温度の最後にペア（x、y）を挿入します
      • 温度の各ペア（i、j）について、
        • matrix [i、j]：=2
      • twos：=temp
      • ans：=ans +（2が空でない場合は1、それ以外の場合は0）
    • ones=行列内の1の数を数える
    • 1が0の場合はansを返し、それ以外の場合は-1を返します

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

例

class Solution:
   def solve(self, matrix):
      ans = 0
      twos = []
      for i in range(len(matrix)):
         for j in range(len(matrix[0])):
            if matrix[i][j] == 2:
               twos.append((i, j))
      while twos:
         temp = []
         for i, j in twos:
            for x, y in [(i + 1, j), (i, j + 1), (i - 1, j), (i, j - 1)]:
               if 0 <= x < len(matrix) and 0 <= y < len(matrix[0]) and matrix[x][y] == 1:
                  temp.append((x, y))
         for i, j in temp:
            matrix[i][j] = 2
         twos = temp
         ans += 1 if twos else 0

      ones = sum(int(matrix[i][j] == 1) for i in range(len(matrix)) for j in range(len(matrix[0])))
      return ans if ones == 0 else -1

ob = Solution()
matrix = [
   [1, 2, 1],
   [1, 0, 1],
   [1, 1, 1]
]
print(ob.solve(matrix))

入力

matrix = [  
[1, 2, 1],  
[1, 0, 1],  
[1, 1, 1] ]

出力

4