题目:
在给定的网格中,每个单元格可以有以下三个值之一:
值 0 代表空单元格;
值 1 代表新鲜橘子;
值 2 代表腐烂的橘子。
每分钟,任何与腐烂的橘子(在 4 个正方向上)相邻的新鲜橘子都会腐烂。
返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能,返回 -1。
示例 1:
坏句子
输入:[[2,1,1],[1,1,0],[0,1,1]]
输出:4
示例 2:
输入:[[2,1,1],[0,1,1],[1,0,1]]
输出:-1
解释:左下角的橘子(第 2 行, 第 0 列)永远不会腐烂,因为腐烂只会发生在 4 个正向上。
示例 3:
输入:[[0,2]]
输出:0
解释:因为 0 分钟时已经没有新鲜橘子了,所以答案就是 0 。
提示:
1 <= grid.length <= 10
1 <= grid[0].length <= 10
grid[i][j] 仅为 0、1 或 2
题目的理解:
分几个小步骤思考:
1. 网格中是否还有正常的橘子。
2. 网格中坏橘子的位置。
3. 怀橘子是否传染能传染旁边的橘子,如有则直接传染。
4. 如果没法传染旁边的橘子,那么结束。
python实现
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
if self.all_bad(grid):
return 0
minutes = 0
while self.all_bad(grid) is False:
result = self.infect(grid)
if result:
minutes += 1
else:
if self.all_bad(grid) is False:
minutes = -1
break
return minutes
def infect(self, grid: List[List[int]]) -> bool:
bads = list()
m = len(grid)
n = len(grid[0])
for row in range(m):
for column in range(n):
if 2 == grid[row][column]:
bads.append((row, column))
if 0 >= len(bads):
return False
is_infected = False
for bad in bads:
row, column = bad
if row > 0:
if 1 == grid[row - 1][column]:
is_infected = True
grid[row - 1][column] = 2
if row + 1 < m:
if 1 == grid[row + 1][column]:
is_infected = True
grid[row + 1][column] = 2
if column > 0:
if 1 == grid[row][column - 1]:
is_infected = True
grid[row][column - 1] = 2
if column + 1 < n:
if 1 == grid[row][column + 1]:
is_infected = True
grid[row][column + 1] = 2
return is_infected
def all_bad(self, grid: List[List[int]]) -> bool:
for row in grid:
if row.count(1) > 0:
return False
return True
提交
马马虎虎成绩马马虎虎,但是感觉到思路还是很清晰的。
// END 今天动手买了《华友钴业》的股票,感觉会有一波吧。
网友评论