---
# System prepended metadata

title: '**Leetcode筆記(Number of Islands)**'
tags: [Amazon, graph, medium, microsoft, leetcode]

---

# **Leetcode筆記(Number of Islands)**


:::info
:information_source: 題目 : Number of Islands, 類型 : graph , 等級 : medium
日期 : 2023/04/15，2023/05/16，2023/07/13，2023/09/16，2023/11/20，2023/11/25，2024/02/13，2024/10/24，2025/02/17
:::


### 嘗試

2023/05/16
時間複雜度是 O(m * n)，其中 m 是矩陣的行數，n 是矩陣的列數。因為我們需要遍歷整個矩陣
空間複雜度是 O(m * n)
```python
dfs (stack)


class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        record = []
        visited = set()


        def dfs(r, c):
            while record:
                row, col = record.pop()
                visited.add((row, col))
                for dr, dc in dirs:
                    nr, nc = row + dr, col + dc
                    if (0 <= nr < m and 0 <= nc < n and grid[nr][nc] == "1" and (nr, nc) not in visited):
                        record.append((nr, nc))
                        visited.add((nr, nc))


        res = 0
        # 因為不連續 所以另外要用一個迴圈
        for r in range(m):
            for c in range(n):
                # 這樣被第一個node連著都在visited
                if grid[r][c] == "1" and (r, c) not in visited:
                    # 初始化
                    record.append([r, c])
                    dfs(r, c)
                    res += 1
        
        return res
```
2023/05/16
```python
bfs (queue)


class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        # bfs (queue)
        m, n = len(grid), len(grid[0])
        dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        q = deque()
        visited = set()


        def bfs(r, c):
            while q:
                row, col = q.popleft()
                visited.add((row, col))
                for dr, dc in dirs:
                    nr, nc = row + dr, col + dc
                    if (0 <= nr < m and 0 <= nc < n and grid[nr][nc] == "1" and (nr, nc) not in visited):
                        q.append((nr, nc))
                        visited.add((nr, nc))


        res = 0
        for r in range(m):
            for c in range(n):
                if grid[r][c] == "1" and (r, c) not in visited:
                    # 初始化
                    q.append([r, c])
                    bfs(r, c)
                    res += 1
        
        return res
```
2023/07/13

```python
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        visited = set()
        dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        count = 0

        def dfs(r, c):
            if r < 0 or c < 0 or r >= m or c >=n or (r, c) in visited or grid[r][c] == "0":
                return

            visited.add((r, c))
            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                dfs(nr, nc)

            return

        for r in range(m):
            for c in range(n):
                if grid[r][c] == "1" and (r, c) not in visited:
                    dfs(r, c)
                    count += 1
        
        return count
```
2023/09/16
不能直接船grid[nr][nc]，如果nr nc這時候本身就超過範圍，那就會錯誤
要先檢查範圍再取grid的值
```python
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        m, n = len(grid), len(grid[0])
        count = 0
        visited = set()

        def bfs(r, c):
            if r < 0 or c < 0 or r >= m or c >= n or grid[r][c] == "0" or (r, c) in visited:
                return False
            
            visited.add((r, c))

            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                bfs(nr, nc)
                    
            return True

        for r in range(m):
            for c in range(n):
                if bfs(r, c):
                    count += 1 
        return count
```
2023/11/20
```python
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        visited = set()
        dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        res = 0
        R, C = len(grid), len(grid[0])

        def bfs(r, c):
            if r < 0 or r >= R or c < 0 or c >= C or grid[r][c] == "0" or (r, c) in visited:
                return False
            
            visited.add((r,c))

            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                bfs(nr, nc)
            
            return True
        
        for r in range(R):
            for c in range(C):
                if bfs(r, c):
                    res += 1
        
        return res
```
2023/11/25
```python
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        n, m = len(grid), len(grid[0])
        res = 0
        visited = set()
        dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]

        def bfs(r, c, grid):
            if r < 0 or c < 0 or r >= n or c >= m or (r, c) in visited or grid[r][c] == "0":
                return False
            
            visited.add((r, c))
            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                bfs(nr, nc, grid)
            
            return True


        for r in range(n):
            for c in range(m):
                if bfs(r, c, grid):
                    res += 1
                
        return res
```
2024/02/13
```python
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        visited = set()
        res = 0
        dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        n, m = len(grid), len(grid[0])

        def bfs(r, c):
            if r < 0 or c < 0 or r >= n or c >= m or (r, c) in visited or grid[r][c] == "0":
                return 
    
            visited.add((r, c))
            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                bfs(nr, nc)

            return True

        for r in range(n):
            for c in range(m):
                if bfs(r, c):
                    res += 1

        return res 
```

2024/10/24
```python
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        self.res = 0
        self.n, self.m = len(grid), len(grid[0])
        self.dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        self.visited = set()

        for r in range(self.n):
            for c in range(self.m):
                if self.dfs(grid, r, c):
                    self.res += 1
        return self.res 
    
    def dfs(self, grid, r, c):
        if r < 0 or r >= self.n or c < 0 or c >= self.m or (r, c) in self.visited or grid[r][c] == "0":
            return
        
        self.visited.add((r, c))
        
        for dr, dc in self.dirs:
            nr, nc = r + dr, c + dc
            self.dfs(grid, nr, nc)

        return True
```
2024/10/24
面試Google前準備，dfs / bfs 加油!!
```python
# bfs

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        self.n, self.m = len(grid), len(grid[0])
        self.dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        visited = set()
        res = 0

        for r in range(self.n):
            for c in range(self.m):
                if grid[r][c] == "1" and (r, c) not in visited:
                    self.bfs(grid, r, c, visited)
                    res += 1
        return res

    def bfs(self, grid, r, c, visited): 
        q = deque()
        q.append((r, c))
        visited.add((r, c))
        while q:
            r, c = q.popleft()
            for dr, dc in self.dirs:
                nr, nc = r + dr, c + dc
                if 0 <= nr < self.n and 0 <= nc < self.m and (nr, nc) not in visited and grid[nr][nc] == "1":
                    visited.add((nr, nc))
                    q.append((nr, nc))
        return 
```
```python
# dfs

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        res = 0
        self.n, self.m = len(grid), len(grid[0])
        self.dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        visited = set()

        for r in range(self.n):
            for c in range(self.m):
                if self.dfs(grid, r, c, visited):
                    res += 1
        return res 
    
    def dfs(self, grid, r, c, visited):
        if r < 0 or r >= self.n or c < 0 or c >= self.m or (r, c) in visited or grid[r][c] == "0":
            return False
        
        visited.add((r, c))
        
        for dr, dc in self.dirs:
            nr, nc = r + dr, c + dc
            if 0 <= nr < self.n and 0 <= nc < self.m and (nr, nc) not in visited and grid[nr][nc] == "1":
                self.dfs(grid, nr, nc, visited)

        return True
```
2025/02/17
```python
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        self.grid = grid
        self.n, self.m = len(grid), len(grid[0])
        res = 0
        self.visited = set()
        self.dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]

        for r in range(self.n):
            for c in range(self.m):
                if (r, c) not in self.visited and self.grid[r][c] == "1":
                    self.bfs(r, c)
                    res += 1

        return res

    def bfs(self, r, c):
        if r < 0 or c < 0 or r >= self.n or c >= self.m or (r, c) in self.visited or self.grid[r][c] == "0":
            return

        self.visited.add((r, c))
        for dr, dc in self.dirs:
            nr, nc = r + dr, c + dc
            self.bfs(nr, nc) 

```


---
### **優化**

時間複雜度O(n)，空間複雜度O(n)

```python
# dfs

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        ROW, COL = len(grid), len(grid[0])
        visit = set()

        def dfs(r, c):
            if (r < 0 or c < 0 or r == ROW or c == COL or 
                grid[r][c] == "0" or (r, c) in visit):
                return 
            
            visit.add((r, c))

            dfs(r + 1, c)
            dfs(r - 1, c)
            dfs(r, c + 1)
            dfs(r, c - 1)

            
        res = 0
        for r in range(ROW):
            for c in range(COL):
                # 防止已經被連起來的島嶼又被dfs一次
                if grid[r][c] == "1" and (r, c) not in visit:
                    dfs(r, c) # 都return(都撞到0了)才會通過此
                    res += 1
        
        return res
```
```python
# bfs_1

from collections import deque

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        ROW, COL = len(grid), len(grid[0])
        visit = set()

        # iterative
        def bfs(r, c):
            # 初始化
            queue = deque([(r, c)])
            visit.add((r, c))
            
            while queue:
                r, c = queue.popleft()

                directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
                for dr, dc in directions:
                    nr, nc = r + dr, c + dc # 取代四點去循環
                    if (nr < 0 or nc < 0 or nr == ROW or nc == COL or 
                        grid[nr][nc] == "0" or (nr, nc) in visit):
                        continue # 跳下一個循環
                    # 合格的話
                    queue.append((nr, nc)) 
                    visit.add((nr, nc))

            
        res = 0
        for r in range(ROW):
            for c in range(COL):
                if grid[r][c] == "1" and (r, c) not in visit:
                    bfs(r, c) # q為空才會通過此
                    res += 1
        
        return res
```
```python
# bfs_2

from collections import deque

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        ROW, COL = len(grid), len(grid[0])
        visit = set()

        # iterative
        def bfs(r, c):
            # 初始化
            queue = deque([(r, c)])
            #visit.add((row, col))
            
            while queue:
                r, c = queue.popleft()
                
                if (r, c) not in visit:
                    visit.add((r, c))

                    if r - 1 >= 0 and grid[r - 1][c] == '1':
                        queue.append((r - 1, c))
                    if r + 1 < ROW and grid[r + 1][c] == '1':
                        queue.append((r + 1, c))
                    if c - 1 >= 0 and grid[r][c - 1] == '1':
                        queue.append((r, c - 1))
                    if c + 1 < COL and grid[r][c + 1] == '1':
                        queue.append((r, c + 1))

            
        res = 0
        for r in range(ROW):
            for c in range(COL):
                if grid[r][c] == "1" and (r, c) not in visit:
                    bfs(r, c) # q為空才會通過此
                    res += 1
        
        return res
```
---


**:warning: 錯誤語法** 
:::warning
q為append
:::


**:thumbsup:學習** 
:::success

:::

**思路**


**講解連結**
https://www.youtube.com/watch?v=pV2kpPD66nE
Provided by. NeetCode
https://blog.csdn.net/qq_37821701/article/details/108414557
https://blog.csdn.net/fuxuemingzhu/article/details/81126995

###### tags: `graph` `medium` `leetcode`