994. Rotting Oranges

[fockspaces]

use BFS and round technique to infect the fresh orange

1. collect the rotten orange into queue, meanwhile counting the fresh orange number
2. if there's no fresh orange, return rounds = 0
3. start BFS, if found fresh orange nearby, rotten it ( = 2) and add it into queue, decrease the fresh_orange amounts
4. once no fresh orange or no rotten oranges in queue, return -1

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        queue = []
        m, n = len(grid), len(grid[0])
        fresh_oranges = m * n
        rounds = 0
        directions = [(0,1), (0,-1), (1,0), (-1,0)]
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 2:
                    queue.append((i, j))
                if grid[i][j] != 1:
                    fresh_oranges -= 1

        if fresh_oranges == 0:
            return rounds
        while queue:
            if fresh_oranges == 0:
                return rounds
            k = len(queue)
            for _ in range(k):
                row, col = queue.pop(0)
                for i, j in directions:
                    if 0 <= row + i < m and 0 <= col + j < n and grid[row + i][col + j] == 1:
                        queue.append((row + i, col + j))
                        grid[row + i][col + j] = 2
                        fresh_oranges -= 1
            rounds += 1
        return -1

[fockspaces]

GPT imrprove: remove redudant check for fresh oranges

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        queue = []
        m, n = len(grid), len(grid[0])
        fresh_oranges = 0
        rounds = 0
        directions = ((0,1), (0,-1), (1,0), (-1,0))
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 2:
                    queue.append((i, j))
                if grid[i][j] == 1:
                    fresh_oranges += 1

        while queue and fresh_oranges > 0:
            k = len(queue)
            for _ in range(k):
                row, col = queue.pop(0)
                for i, j in directions:
                    if 0 <= row + i < m and 0 <= col + j < n and grid[row + i][col + j] == 1:
                        queue.append((row + i, col + j))
                        grid[row + i][col + j] = 2
                        fresh_oranges -= 1
            rounds += 1
        return -1 if fresh_oranges > 0 else rounds