题解 | #岛屿数量#

BFS宽度优先搜索

class Solution {
public:
    /**
     * 判断岛屿数量
     * @param grid char字符型vector<vector<>> 
     * @return int整型
     */
    void bfs(vector<vector<char> >& grid, int i, int j) {
        int dx[4] = {1, -1, 0, 0};
        int dy[4] = {0, 0, 1, -1};
        grid[i][j] = '#';
        for(int k = 0; k < 4; k++) {
            int ix, jx;
            ix = i + dx[k], jx = j + dy[k];
            if(ix >= 0 && ix < grid.size() && jx >= 0 && jx < grid[0].size() && grid[ix][jx] == '1') {
                bfs(grid, ix, jx);
            }
        }
    }

    int solve(vector<vector<char> >& grid) {
        // write code here
        int res = 0;
        for(int i = 0; i < grid.size(); i++)
            for(int j = 0; j < grid[0].size(); j++)
                if(grid[i][j] == '1') {
                    res++;
                    bfs(grid, i, j);
                }
        return res;
    }

};