994. Rotting Oranges

Description:

You are given an m x n grid where each cell can have one of three values:

• 0 representing an empty cell,
• 1 representing a fresh orange, or
• 2 representing a rotten orange.

Every minute, any fresh orange that is 4-directionally adjacent 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.

 

'''
[1] bfs)

idea::
0. when don't consider all 2, step will be weird
1. find all 2 and push row index and col index of 2 to queue
2. if there is no 2 ==> if there is 1 return -1, else return 0
3. from all 2, start rotting, calculate step by bfs
4. after, find remaining 1
5. if there is 1, return -1, else return step

code::
(below)

- m==len(grid), n==len(grid[0])
-T/C: O(m*n) # O(m*n) for finding all 2, O(m*n) for bfs, O(m*n) for finding remaining 1
-S/C: O(m*n) # when all grid[r][c]==2, then queue size will be m*n
'''

from collections import deque
class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        m=len(grid)
        n=len(grid[0])
        
        queue=deque()
        
        # find all 2 and push row index and col index to queue
        # if there is no 2 -> if there is 1 return -1, else return 0
        flag_1=False
        for r in range(m):
            for c in range(n):
                if grid[r][c]==2:
                    queue.append([r,c])
                if grid[r][c]==1:
                    flag_1=True
        
        if len(queue)==0:
            if not flag_1:
                return 0
        
        step=-1
        while queue:
            step+=1
            size=len(queue)
            
            for time in range(size):
                cur=queue.popleft()
                
                # above
                if cur[0]-1>=0 and grid[cur[0]-1][cur[1]]==1:
                    queue.append([cur[0]-1,cur[1]])
                    grid[cur[0]-1][cur[1]]=2
                
                # below
                if cur[0]+1<m and grid[cur[0]+1][cur[1]]==1:
                    queue.append([cur[0]+1,cur[1]])
                    grid[cur[0]+1][cur[1]]=2
                
                # left
                if cur[1]-1>=0 and grid[cur[0]][cur[1]-1]==1:
                    queue.append([cur[0],cur[1]-1])
                    grid[cur[0]][cur[1]-1]=2
                
                # right
                if cur[1]+1<n and grid[cur[0]][cur[1]+1]==1:
                    queue.append([cur[0],cur[1]+1])
                    grid[cur[0]][cur[1]+1]=2
        
        for r in range(m):
            for c in range(n):
                if grid[r][c]==1:
                    return -1
        return step