# **Leetcode筆記(Rotting Oranges)**
:::info
:information_source: 題目 : Rotting Oranges, 類型 : graph , 等級 : medium
日期 : 2023/05/16，2023/07/14，2024/02/14，2024/09/25
:::
### 嘗試
時間複雜度：假設矩陣中有N個單元格，其中有M個腐爛的橘子。在最壞的情況下，所有的腐爛橘子都需要進行BFS遍歷，而每個單元格最多被訪問一次。
因此，總的時間複雜度為O(M*N)。
空間複雜度方面，你使用了一個佇列q來存儲腐爛的橘子。由於最多只會存儲M個腐爛橘子，所以佇列的最大長度為M。
此外，你還使用了一個集合visited來記錄已經訪問過的橘子的坐標。在最壞的情況下，所有的單元格都需要被訪問一次，所以集合visited最多佔用N個單元格的額外空間。
因此，總的空間複雜度為O(M+N)。 Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
# 適用bfs 因為是類似一層一層往外看
# 而不是先走到最深處
m, n = len(grid), len(grid[0])
```python
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
# 適用bfs 因為是類似一層一層往外看
# 而不是先走到最深處
m, n = len(grid), len(grid[0])
dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
q = deque()
visited = set()
fresh_ori, fresh_step = 0, 0 # 紀錄bfs次數
fresh = 0 # 真實為1的水果次數
for r in range(m):
for c in range(n):
if grid[r][c] == 2:
q.append((r, c))
elif grid[r][c] == 1:
fresh += 1
# 完全沒有正常水果
if fresh == 0:
return 0
while q:
step = len(q)
# 把這一輪內的q先完全清空
# 這樣就可以記錄"輪"的次數
for i in range(step):
row, col = q.popleft()
visited.add((row, col))
for dr, dc in dirs:
nr, nc = dr + row, dc + col
if 0 <= nr < m and 0 <= nc < n and (nr, nc) not in visited and grid[nr][nc] == 1:
visited.add((nr, nc))
q.append((nr, nc))
fresh_ori += 1
fresh_step += 1
if fresh_ori == fresh:
return fresh_step - 1 # 第一輪不算
else:
return -1
```
2023/07/13
因為需要算階層數，所以用bfs的方法，創造一個deque，注意visited是在通過下面if條件後才加入
```python
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
q = deque()
visited = set()
fresh, becoRotten, step = 0, 0, 0
# 統計腐爛與新鮮的
for r in range(m):
for c in range(n):
if grid[r][c] == 2:
q.append((r, c))
if grid[r][c] == 1:
fresh += 1
# 沒有新鮮的直接返回
if fresh == 0:
return 0
while q:
length = len(q)
for _ in range(length):
r, c = q.popleft()
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and (nr, nc) not in visited and grid[nr][nc] == 1:
q.append((nr, nc))
visited.add((nr, nc)) # 這時候就要加入visited 避免重複加入 使step計算上有錯誤
becoRotten += 1
step += 1
if becoRotten == fresh:
return step - 1 # 第一輪不算
return -1
```
2023/12/09
```python
"""
count the number of fresh
q = deque()
start from the rotten
visited -> store o already rotten
while q:
keep pop from q
1. check four dirrection
2. add more o (next layer) to q
3. add o to visited
track the layer
check if fresh == len(visited)
"""
import collections
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
n, m = len(grid), len(grid[0])
# init BFS
q = deque()
visited = set()
# count the fresh orange
fresh = 0
for r in range(n):
for c in range(m):
if grid[r][c] == 1:
fresh += 1
elif grid[r][c] == 2:
q.append((r, c))
visited.add((r, c))
if fresh == 0:
return 0
dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
step = 0
# start BFS
while q:
layer = len(q)
for _ in range(layer):
r, c = q.popleft()
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < m and (nr, nc) not in visited and grid[nr][nc] == 1:
q.append((nr, nc))
visited.add((nr, nc))
fresh -= 1
print(fresh)
step += 1
if fresh == 0:
return step - 1
return -1
```
2024/02/14
```python
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
n, m = len(grid), len(grid[0])
dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
fresh_to_rotten, fresh = 0, 0
q = deque()
visited = set()
# collection the rotten orange
for r in range(n):
for c in range(m):
if grid[r][c] == 2:
q.append((r, c))
visited.add((r, c))
if grid[r][c] == 1:
fresh += 1
# special case
if fresh == 0:
return 0
step = 0
while q:
length = len(q)
for _ in range(length):
rotten_r, rotten_c = q.popleft()
for dr, dc in dirs:
new_r, new_c = rotten_r + dr, rotten_c + dc
if 0 <= new_r < n and 0 <= new_c < m and grid[new_r][new_c] == 1 and (new_r, new_c) not in visited:
q.append((new_r, new_c))
visited.add((new_r, new_c))
fresh_to_rotten += 1
step += 1
if fresh_to_rotten == fresh:
return step - 1
else:
return -1
```
2024/09/25
```python
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
n, m = len(grid), len(grid[0])
fresh, normal = 0, 0
q = deque()
visited = set()
dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
for r in range(n):
for c in range(m):
if grid[r][c] == 0:
normal += 1
if grid[r][c] == 1:
fresh += 1
if grid[r][c] == 2:
q.append((r, c))
visited.add((r, c))
if normal == n * m: # 處理都是0
return 0
fresh_count = 0
step = 0
while q:
l = len(q)
for _ in range(l):
r, c = q.popleft()
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < m and (nr, nc) not in visited and grid[nr][nc] == 1:
fresh_count += 1
q.append((nr, nc))
visited.add((nr, nc))
step += 1
if fresh_count == fresh:
return step - 1
else:
return -1
```
---
### **優化**
```python
```
---
**:warning: 錯誤語法**
:::warning
:::
**:thumbsup:學習**
:::success
:::
**思路**
**講解連結**
Provided by. NeetCode
###### tags: `graph` `medium` `leetcode`
Sign in with Wallet
Connect another wallet