您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

LeetCode 200 Number of Islands：DFS/BFS 檢測連通分量經典題

編輯：關於C++

問題描述

給定 m×n 的二維網格，'1' 代表陸地，'0' 代表水。島嶼是被水包裹、且水平/垂直方向相連的陸地。求島嶼數量。四邊假設被水包圍。

核心思路：洪水填充

遍歷網格，遇到未訪問的 '1'，計數器+1，啟動 DFS/BFS 將其連通分量全部標記為已訪問（或直接修改為 '0'/'2'）。

C 語言 DFS 實現（原地修改）

int R, C;
int dir[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};
char** G;
bool** vis;

void dfs(int r, int c) {
    vis[r][c] = true;
    for (int i = 0; i < 4; ++i) {
        int nr = r + dir[i][0], nc = c + dir[i][1];
        if (nr >= 0 && nr < R && nc >= 0 && nc < C 
            && !vis[nr][nc] && G[nr][nc] == '1')
            dfs(nr, nc);
    }
}

int numIslands(char** grid, int numRows, int numCols) {
    G = grid; R = numRows; C = numCols;
    vis = malloc(R * sizeof(bool*));
    for (int i = 0; i < R; ++i) {
        vis[i] = calloc(C, sizeof(bool));
    }
    int ans = 0;
    for (int i = 0; i < R; ++i)
        for (int j = 0; j < C; ++j)
            if (!vis[i][j] && G[i][j] == '1') {
                ++ans;
                dfs(i, j);
            }
    for (int i = 0; i < R; ++i) free(vis[i]);
    free(vis);
    return ans;
}

優化：原地標記避免額外訪問數組

void dfs(char** grid, int r, int c, int R, int C) {
    if (r < 0 || r >= R || c < 0 || c >= C || grid[r][c] != '1') return;
    grid[r][c] = '0';  // 標記為水
    dfs(grid, r+1, c, R, C);
    dfs(grid, r-1, c, R, C);
    dfs(grid, r, c+1, R, C);
    dfs(grid, r, c-1, R, C);
}

// 主函數中直接調用，無需 vis 數組

Java BFS 實現（併發安全、無遞歸棧溢出風險）

class Pair { int x, y; Pair(int x, int y) { this.x = x; this.y = y; } }

public int numIslands(char[][] grid) {
    if (grid == null || grid.length == 0) return 0;
    int R = grid.length, C = grid[0].length;
    int ans = 0;
    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < C; ++j) {
            if (grid[i][j] == '1') {
                ++ans;
                Queue<Pair> q = new LinkedList<>();
                q.offer(new Pair(i, j));
                grid[i][j] = '0';
                while (!q.isEmpty()) {
                    Pair p = q.poll();
                    int[] dr = {1,-1,0,0}, dc = {0,0,1,-1};
                    for (int k = 0; k < 4; ++k) {
                        int nr = p.x + dr[k], nc = p.y + dc[k];
                        if (nr >= 0 && nr < R && nc >= 0 && nc < C && grid[nr][nc] == '1') {
                            grid[nr][nc] = '0';
                            q.offer(new Pair(nr, nc));
                        }
                    }
                }
            }
        }
    }
    return ans;
}