使用python编写一个查找烧毁所有树木所需时间的程序

假设我们有一个2D矩阵，表示一片森林，其中有三种类型的单元格：0表示空单元格，1表示树单元格，2表示燃烧的树单元格。每天，当周围（上下左右，不包括对角线）有一棵燃烧的树时，一棵树会着火。我们必须找到每棵树燃烧所需的天数。如果不可能，则返回-1。

因此，如果输入是：

1	2	1
1	0	1
1	1	1

则输出为4。

要解决此问题，我们需要执行以下步骤：

• ans := 0
• twos := 新列表
• 对于矩阵的每一行 i，执行以下操作:
  • 对于矩阵的每一列 j，执行以下操作:
    • 如果矩阵[i, j]与2相同，则：
    • 将(i, j)对插入到twos的末尾中
    • 当twos不为空时，执行以下操作:
    • temp := 一个新列表
    • 将twos中的每个对(i, j)遍历，执行以下操作：
      • 将每个对(x, y)在 [(i + 1, j), (i, j + 1), (i-1, j), (i, j -1)] 中的值遍历:
      • 如果x和y在矩阵的范围内且matrix[x, y]等于1，则:
        • 将对(x, y)插入到temp的末尾
    • 对于temp中的每一个对(i, j)，执行以下操作:
    • 用2替换 matrix[i, j]
    • twos = temp
    • 如果twos不为空，则ans= ans + 1
• 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