# [LeetCode] 200. Number of Islands (Medium)

###### tags: `LeetCode`

## 題目
給定一個 $m \times n$ 的二維矩陣`grid`，裡面只包含 `"0"`（代表水）和 `"1"`（代表陸地），計算這個矩陣上面島的數量。

所謂的島指的是四面環水，由水平或垂直的相鄰陸地連接而成的區域。 在這裡我們假設`grid`的四個邊緣都被水包圍。

## 限制條件
* `m == grid.length`
* `n == grid[i].length`
* `1 <= m, n <= 300`
* `grid[i][j]` is `"0"` or `"1"`.

## 範例
* Example 1:

    輸入: grid = [
      ["1","1","1","1","0"],
      ["1","1","0","1","0"],
      ["1","1","0","0","0"],
      ["0","0","0","0","0"]
    ]

    輸出: 1

* Example 2:

    輸入: grid = [
      ["1","1","0","0","0"],
      ["1","1","0","0","0"],
      ["0","0","1","0","0"],
      ["0","0","0","1","1"]
    ]
    
    輸出: 3

## 解答
### 基於DFS的解法
這題我們可以基於DFS來做。DFS的概念，是從一個起點 $v$ 開始，盡可能的遠離 $v$，直到無法再走下去時再回溯去找另一條尚未尋訪過的路徑。因此在尋訪時我們必須將已經尋訪過的頂點標記為visited（已尋訪），直到沒有任何未尋訪的頂點為止。

對於這道題目，我們必須分別尋訪每個島，並把尋訪過的陸地（`"1"`）標記為水（`"0"`）。

實作DFS的方法有兩種：遞迴和stack。

* 使用遞迴的解法
在這邊因為我們不確定要從哪邊開始尋訪，所以我們選擇迭代所有地圖上的點，找出合適的起點（也就是陸地），再從該點開始做DFS。用遞迴來實作DFS和樹的尋訪是很類似的，演算法的步驟如下：
1. 標記目前所在頂點為visited並對該節點進行操作（如print出節點的value）
2. 尋訪相鄰的頂點，在那些頂點上依序呼叫遞迴函式

使用遞迴的方式來解本題，其Python code如下：

    class Solution:
        def numIslands(self, grid: List[List[str]]) -> int:
            # 檢查整片地圖的 size，如果橫排(row)數量是0則沒有島，直接回傳0
            rows = len(grid)
            cols = len(grid[0])
            
            if rows == cols == 1:
                return 1 if grid[0][0] == "1" else 0
            
            def dfs(r, c):
                # 相當於標記為 visited
                grid[r][c] = "0"
                # 依序在相鄰的頂點呼叫遞迴函式
                if r - 1 >= 0 and grid[r - 1][c] == "1":
                    dfs(r - 1, c)
                if r + 1 < rows and grid[r + 1][c] == "1":
                    dfs(r + 1, c)
                if c - 1 >= 0 and grid[r][c - 1] == "1":
                    dfs(r, c - 1)
                if c + 1 < cols and grid[r][c + 1] == "1":
                    dfs(r, c + 1)

            # 島的總數先初始化為 0
            n = 0 
            for r in range(rows):
                for c in range(cols):
                    if grid[r][c] == "1": 
                        # 發現新的島，把整個島尋訪一次
                        n += 1
                        dfs(r, c)
            return n

* 使用stack的解法
用stack來實作DFS的概念其實就是把前面的遞迴寫成迴圈。我們知道遞迴的背後就是一個function call的stack，這邊我們將相鄰的頂點放入stack裡面，再按照stack的後進先出順序進行尋訪。

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid:
            return 0
        
        rows = len(grid)
        if rows == 0:
            return 0
        
        cols = len(grid[0])
        n = 0
        
        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == "1":
                    n += 1
                    grid[i][j] = "0"
                    stack = [(i, j)]
                    
                    while stack:
                        r, c = stack.pop(-1)
                        if r - 1 >= 0 and grid[r - 1][c] == "1":
                            stack.append((r - 1, c))
                            grid[r - 1][c] = "0"
                        if r + 1 < rows and grid[r + 1][c] == "1":
                            stack.append((r + 1, c))
                            grid[r + 1][c] = "0"
                        if c - 1 >= 0 and grid[r][c - 1] == "1":
                            stack.append((r, c - 1))
                            grid[r][c - 1] = "0"
                        if c + 1 < cols and grid[r][c + 1] == "1":
                            stack.append((r, c + 1))
                            grid[r][c + 1] = "0"
                            
                            
        return n

### 基於BFS的解法
我們當然也可以用BFS來解這題，只要把前面DFS的stack版本改成使用queue即可，其他的概念都和基於DFS的解法類似，不再多做說明：

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid:
            return 0
        
        rows = len(grid)
        if rows == 0:
            return 0
        
        cols = len(grid[0])
        n = 0
        
        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == "1":
                    n += 1
                    grid[i][j] = "0"
                    queue = [(i, j)]
                    
                    while queue:
                        r, c = queue.pop(0)
                        if r - 1 >= 0 and grid[r - 1][c] == "1":
                            queue.append((r - 1, c))
                            grid[r - 1][c] = "0"
                        if r + 1 < rows and grid[r + 1][c] == "1":
                            queue.append((r + 1, c))
                            grid[r + 1][c] = "0"
                        if c - 1 >= 0 and grid[r][c - 1] == "1":
                            queue.append((r, c - 1))
                            grid[r][c - 1] = "0"
                        if c + 1 < cols and grid[r][c + 1] == "1":
                            queue.append((r, c + 1))
                            grid[r][c + 1] = "0"
                            
                            
        return n