994. Rotting Oranges

Question: Rotting Oranges

Solution

想法：

multi source BFS → queue

1. for loop 全部的橘子一遍
   1. 先把 rotten source 找出來，存入 queue
   2. 把 fresh 數量找出來
2. 當 queue 與 fresh 都有資料的時候
   1. for loop 所有 q 裡的項目
   2. pop 項目
   3. 把它變成 rotten
   4. 找他的鄰居
   5. 如果鄰居是合法的，就把鄰居放入 queue
3. 每次 rotten 一個橘子 fresh -= 1
4. 最後 fresh > 0 return -1; = 0 return time

from collections import deque

class Solution(object):

def orangesRotting(self, grid):

"""

:type grid: List[List[int]]

:rtype: int

"""

rows, columns = len(grid), len(grid[0])

time, fresh = 0, 0

def rot(r, c, fresh):

if (r > -1 and

c > -1 and

r < rows and

c < columns and

grid[r][c] == 1):

q.append([r, c])

grid[r][c] = 2

fresh -= 1

return fresh

# find rotten source

q = deque(list())

for r in range(rows):

for c in range(columns):

if grid[r][c] == 2:

q.append([r, c])

elif grid[r][c] == 1:

fresh += 1

while q and fresh > 0:

for i in range(len(q)):

r, c = q.popleft()

grid[r][c] = 2

# rot adjacent

fresh = rot(r + 1, c, fresh)

fresh = rot(r - 1, c, fresh)

fresh = rot(r, c + 1, fresh)

fresh = rot(r, c - 1, fresh)

time += 1

return time if fresh == 0 else -1

Video Solution