Jianbo Dai's

mq056.腐烂的橘子

 
  • Jan 24, 2021

题目链接

这题是一个bfs，不过稍微复杂一点的是bfs的起始点不止一个而是有很多个源头。其实还是比较好写的，直接参考了官方的代码，因为有几个不常用的小技巧可以讲一下。首先，我之前在枚举方向时一般用一个类似[(0, 1), (0, -1), (1, 0), (-1, 0)]的列表，而在1中的代码中我们直接用一个包含了各个方向改变的元组，并且在生成方向时用了yield而非产生一个列表，这样比较优雅。另外还有在最后判断gird中是否还有新鲜橘子时用的any(1 in row for row in grid)也是我不常用的。

这个算法的时间复杂度是O（NM），空间复杂度是O（NM）。

python:

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        row, col = len(grid), len(grid[0])
        queue = collections.deque()
        for i in range(row):
            for j in range(col):
                if grid[i][j] == 2:
                    queue.append((i, j, 0))

        def neighbours(x, y):
            for nx, ny in ((x-1, y), (x+1, y), (x, y-1), (x, y+1)):
                if 0 <= nx < row and 0 <= ny < col:
                    yield nx, ny

        d = 0
        while queue:
            x, y, d = queue.popleft()
            for nx, ny in neighbours(x, y):
                if grid[nx][ny] == 1:
                    grid[nx][ny] = 2
                    queue.append((nx, ny, d+1))
        
        if any(1 in row for row in grid):
            return -1
        return d
Search