使用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
- 对于矩阵的每一列 j,执行以下操作:
- 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