Python程式：計算燒燬所有樹木所需的天數

假設我們有一個二維矩陣表示一片森林，其中有三種類型的單元格：0 表示空單元格，1 表示樹木單元格，2 表示著火的樹木單元格。每天，當相鄰（上下左右，非對角線）的樹木著火時，一棵樹就會著火。我們必須找到將所有樹木燒燬所需的天數。如果不可能，則返回 -1。

例如，如果輸入如下所示：

1	2	1
1	0	1
1	1	1

則輸出為 4。

為了解決這個問題，我們將遵循以下步驟：

ans := 0
twos := 新列表
對於 i 從 0 到矩陣的行數：
- 對於 j 從 0 到矩陣的列數：
  - 如果 matrix[i, j] 等於 2：
    - 將 (i, j) 對插入到 twos 列表的末尾
  - 當 twos 列表非空時：
    - temp := 新列表
    - 對於 twos 列表中的每個 (i, j) 對：
      - 對於 [(i + 1, j) ,(i, j + 1) ,(i - 1, j) ,(i, j - 1) ] 中的每個 (x, y) 對：
        如果 x 和 y 在矩陣範圍內且 matrix[x, y] 等於 1：
        將 (x, y) 對插入到 temp 列表的末尾
    - 對於 temp 列表中的每個 (i, j) 對：
      - matrix[i, j] := 2
    - twos := temp
    - ans := ans + (如果 twos 非空則為 1，否則為 0)
  - ones = 矩陣中 1 的個數
  - 如果 ones 為 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] ]

輸出

Arnab Chakraborty

更新於：2020年12月2日

735 次瀏覽

開啟您的職業生涯

完成課程獲得認證

開始學習