LeetCode 200 Number of Islands：DFS 求島嶼數量

題目描述

給定 '1'（陸地）'0'（水）組成的網格，計算島嶼數量。島嶼為水平/垂直相鄰陸地連通塊。

DFS 解法

掃描網格，遇 '1' 計數 +1，DFS 將其連通陸地全部標記為 '0'（或訪問標記），避免重複計數。

C++ 實現

int dir[4][2] = {{-1,0},{1,0},{0,1},{0,-1}};
class Solution {
    void dfs(int i, int j, vector<vector<char>>& grid) {
        for (int k = 0; k < 4; ++k) {
            int x = i + dir[k][0], y = j + dir[k][1];
            if (x >= 0 && x < grid.size() && y >= 0 && y < grid[0].size() && grid[x][y] == '1') {
                grid[x][y] = '0';
                dfs(x, y, grid);
            }
        }
    }
public:
    int numIslands(vector<vector<char>>& grid) {
        int cnt = 0;
        for (int i = 0; i < grid.size(); ++i)
            for (int j = 0; j < grid[i].size(); ++j)
                if (grid[i][j] == '1') {
                    grid[i][j] = '0';
                    dfs(i, j, grid);
                    ++cnt;
                }
        return cnt;
    }
};

相關題目

• HDU 1016、HDU 1241：同類 DFS 洪水填充問題。