难度: Easy
原题连接
内容描述
In a given grid, each cell can have one of three values:
the value 0 representing an empty cell;
the value 1 representing a fresh orange;
the value 2 representing a rotten orange.
Every minute, any fresh orange that is adjacent (4-directionally) to a rotten orange becomes rotten.
Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1 instead.
Example 1:
Input: [[2,1,1],[1,1,0],[0,1,1]]
Output: 4
Example 2:
Input: [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.
Example 3:
Input: [[0,2]]
Output: 0
Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.
Note:
1 <= grid.length <= 10
1 <= grid[0].length <= 10
grid[i][j] is only 0, 1, or 2.
思路 1 - 时间复杂度: O(row * col)- 空间复杂度: O(row * col)******
直接模拟，每次直接生成新的grid，直到没有变化
然后我们看看grid中是否还有1，如果有，我们return -1，否则return minutes
class Solution:
def orangesRotting(self, grid: 'List[List[int]]') -> 'int':
row = len(grid)
col = len(grid[0]) if row else 0
nxts = [[0,1],[0,-1],[1,0],[-1,0]]
def helper(grid):
res = [[0] * col for i in range(row)]
visited = set()
change = False
for i in range(row):
for j in range(col):
if grid[i][j] == 2:
for m, n in nxts:
if 0 <= i + m < row and 0 <= j +n < col and grid[i+m][j+n] == 1:
change = True
visited.add((i + m, j + n))
for i in range(row):
for j in range(col):
if (i, j) in visited:
res[i][j] = 2
else:
res[i][j] = grid[i][j]
return [res, change]
new_grid, change = helper(grid)
minutes = 0
while change:
new_grid, change = helper(new_grid)
minutes += 1
if any(new_grid[i][j] == 1 for i in range(row) for j in range(col)):
return -1
return minutes思路 1 - 时间复杂度: O(row * col)- 空间复杂度: O(row * col)******
BFS，设最开始的rotten orange的depth为0，然后一步一步深入，返回最终的depth
class Solution:
def orangesRotting(self, grid: 'List[List[int]]') -> 'int':
row = len(grid)
col = len(grid[0]) if row else 0
nxts = [[0,1],[0,-1],[1,0],[-1,0]]
queue = collections.deque()
for r, lst in enumerate(grid):
for c, val in enumerate(lst):
if val == 2:
queue.append((r, c, 0))
def getNeighbors(i, j):
for m, n in nxts:
if 0 <= i + m < row and 0 <= j +n < col and grid[i+m][j+n] == 1:
yield (i + m, j + n)
depth = 0
while queue:
r, c, depth = queue.popleft()
for x, y in getNeighbors(r, c):
if grid[x][y] == 1:
grid[x][y] = 2
queue.append((x, y, depth+1))
if any(1 in lst for lst in grid):
return -1
return depth