題目
#

leetcode 200 - Number of Islands (題目說明請點連結)

題目簡述
#

給定一個由 ‘1’（陸地）和 ‘0’（水）組成的二維網格，計算島嶼的數量。島嶼被水包圍，並且通過水平或垂直連接相鄰的陸地而形成。

範例
#

Example 1:

Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1
Explanation: 網格中只有一個島嶼，由相連的陸地組成。

Example 2:

Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3
Explanation: 網格中有三個島嶼，分別由不同的相連陸地組成。

解題思路
#

這題要求我們計算二維網格中島嶼的數量。島嶼被水包圍，並且通過水平或垂直連接相鄰的陸地而形成。

解法：深度優先搜索（DFS）

遍歷整個網格，當遇到陸地（‘1’）時，開始 DFS 搜索。
在 DFS 過程中，將訪問過的陸地標記為水（‘0’），避免重複訪問。
每次找到新的陸地時，島嶼計數加一。
使用方向數組來簡化四個方向的搜索。

例子說明
#

grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]

初始情況：count = 0

第一個島嶼：
- 在位置 (0,0) 找到陸地，count++
- DFS 淹沒整個島嶼：(0,0) -> (0,1) -> (1,0) -> (1,1)
- 島嶼計數：count = 1
第二個島嶼：
- 在位置 (2,2) 找到陸地，count++
- DFS 淹沒整個島嶼：(2,2)
- 島嶼計數：count = 2
第三個島嶼：
- 在位置 (3,3) 找到陸地，count++
- DFS 淹沒整個島嶼：(3,3) -> (3,4)
- 島嶼計數：count = 3
最終結果：
- 返回 3

完整程式碼
#

java

class Solution {
    int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // 四個方向的偏移量

    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) return 0; // 邊界條件檢查

        int m = grid.length, n = grid[0].length; // 獲取網格的行數和列數
        int count = 0; // 初始化島嶼計數

        // 遍歷整個網格
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') { // 找到新島嶼
                    count++; // 島嶼計數加一
                    dfs(grid, i, j); // 淹沒這座島嶼
                }
            }
        }
        return count; // 返回島嶼總數
    }

    private void dfs(char[][] grid, int i, int j) {
        int m = grid.length, n = grid[0].length; // 獲取網格的行數和列數
        
        // 邊界條件：超出網格範圍或遇到水
        if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == '0') return;

        grid[i][j] = '0'; // 淹沒該節點（標記為已訪問）

        // 向四個方向進行深度優先搜索
        for(int[] dir : dirs) {
            dfs(grid, i + dir[0], j + dir[1]); // 遞歸搜索相鄰節點
        }
    }
}