题解 | #岛屿数量#

bfs

class Solution {
public:
    /**
     * 判断岛屿数量
     * @param grid char字符型vector<vector<>> 
     * @return int整型
     */
    void bfs(vector<vector<char> >& grid,int row,int col){
        int crow[4] = {1,0,-1,0},ccol[4] = {0,1,0,-1};
        queue<pair<int,int> > qu;
        qu.push(pair<int,int>(row,col));
        while(!qu.empty()){
            pair<int,int> cur = qu.front();
            qu.pop();
            grid[cur.first][cur.second] = '0';
            for(int i = 0;i <= 3;++i){
                int _row = cur.first + crow[i];
                int _col = cur.second + ccol[i];
                if(_row >= 0 && _row < grid.size() && _col >= 0 && _col < grid[0].size() && grid[_row][_col] != '0')
                    qu.push(pair<int,int>(_row,_col));
            }
        }
    }
    int solve(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] != '0'){
                    bfs(grid,i,j);
                    cnt++;
                }
            }
        }
        return cnt;
    }
};