岛屿数量

解題思路

此解法採用深度優先搜尋（DFS）來識別並標記連通的陸地塊。

1. 初始化與遍歷：首先獲取網格的行數 m 和列數 n。定義四個方向向量 dire 用於上下左右移動。初始化計數器 idx 為 0，用於記錄發現的島嶼數量。

2. DFS 函數定義：定義內部函數 dfs(x, y, idx)。當進入該函數時，表示發現了一個新的陸地節點 (x, y)。為了避免重複訪問，將 grid[x][y] 的值修改為 -idx（負數），以此作為「已訪問」的標記。接著，遍歷四個方向，檢查相鄰節點是否在網格範圍內且值為 '1'（未訪問的陸地）。若滿足條件，則遞迴調用 dfs 繼續搜尋該島嶼的其他部分。

3. 主邏輯執行：雙重迴圈遍歷整個網格。當發現 grid[i][j] == '1' 時，表示找到了一個尚未被標記的島嶼的起點。此時將 idx 加 1，並從 (i, j) 開始執行 dfs。DFS 會將該島嶼所有相連的 '1' 都標記為 -idx，確保後續遍歷不會重複計算同一個島嶼。

4. 返回結果：遍歷結束後，idx 的值即為島嶼的總數。

通過的程式碼

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        m= len(grid)
        n = len(grid[0])
        dire = [
            (0,1),
            (1,0),
            (0,-1),
            (-1,0),
        ]
        idx = 0
        def dfs(x, y, idx):
            nonlocal grid
            grid[x][y] = -idx 
            for a, b in dire:
                if 0<=x+a<m and 0<=y+b<n and grid[x+a][y+b] == '1':
                    dfs(x+a, y+b, idx)
                

        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    idx+=1
                    dfs(i, j, idx)
        # print(grid)
        return idx