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] ]

输出

4

更新于：2020年12月2日

735 次浏览

开启您的职业生涯

完成课程获得认证

开始学习
广告