NC109 #岛屿数量#

最基础的DFS了。

lass Solution {
public:
    void dfs(vector<vector<char> >& grid, int i, int j, int w, int h)
    {
        grid[i][j] = '0';
        if(grid[i - 1][j] == '1' && i - 1 >= 0) dfs(grid, i - 1, j, w, h);
        if(grid[i + 1][j] == '1' && i + 1 < w) dfs(grid, i + 1, j, w, h);
        if(grid[i][j - 1] == '1' && j - 1 >= 0) dfs(grid, i, j - 1, w, h);
        if(grid[i][j + 1] == '1' && j + 1 < h) dfs(grid, i, j + 1, w, h);
    }
    int solve(vector<vector<char> >& grid) {
        int w = grid.size(), h = grid[0].size(), count = 0;
        if(w == 0) return 0;
        for(int i = 0; i < w; i++)
            for(int j = 0; j < h; j++)
                if(grid[i][j] == '1')
                    count++, dfs(grid, i, j, w, h);
        return count;
    }
};