994. Rotting Oranges

https://leetcode.com/problems/rotting-oranges/description/

solution

• step 1：统计新鲜水果数据，腐烂水果数据加入队列

• step 2：腐烂水果BFS，更新队列，新鲜水果数据，需要的结果数据

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])

        queue = collections.deque()
        num_fresh = 0

        for i in range(m):
            for j in range(n):
                if grid[i][j] == 2:
                    queue.append((i, j))
                elif grid[i][j] == 1:
                    num_fresh += 1

        if num_fresh == 0:  # 也针对 [[0]]场景
            return 0

        step = -1  # 初始化
        while queue:
            step += 1
            for _ in range(len(queue)):
                x, y = queue.popleft()

                for dx, dy in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
                    new_x = x + dx
                    new_y = y + dy
                    if 0 <= new_x < m and 0 <= new_y < n and grid[new_x][new_y] == 1:
                        queue.append((new_x, new_y))
                        grid[new_x][new_y] = 2  # 这里为什么要在new这里更新, 因为初始的2不在num_fresh里
                        num_fresh -= 1

        return step if num_fresh == 0 else -1

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]]
        queue = collections.deque()
        visited = [[False] * n for _ in range(m)]
        num_fresh = 0

        for i in range(m):
            for j in range(n):
                if grid[i][j] == 2:
                    queue.append([i, j])
                    visited[i][j] = True
                if grid[i][j] == 1:
                    num_fresh += 1

        if num_fresh == 0:  # 也针对 [[0]]场景
            return 0

        step = 0
        while queue:
            for i in range(len(queue)):
                this_i, this_j = queue.popleft()
                for x, y in dirs:
                    new_i = this_i + x
                    new_j = this_j + y
                    if new_i >= 0 and new_i < m and new_j >= 0 and new_j < n and visited[new_i][new_j] == False:
                        if grid[new_i][new_j] == 1:
                            grid[new_i][new_j] = 2
                            queue.append([new_i, new_j])
                            visited[new_i][new_j] = True
                            num_fresh -= 1
            step += 1

        if num_fresh == 0:
            return step - 1
        else:
            return -1

时间复杂度：O() 空间复杂度：O()

follow up

2850. Minimum Moves to Spread Stones Over Grid