---
# System prepended metadata

title: '**Leetcode筆記(Rotting Oranges)**'
tags: [graph, medium, microsoft, leetcode]

---

# **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`