题解 | #岛屿数量#

class Solution {
public:
    bool check(int x,int y,vector<vector<char> >& grid,vector<vector<bool>>&f)
    {
        return x>=0&&x<grid.size()&&y>=0&&y<grid[0].size()&&grid[x][y]=='1'&&!f[x][y];
    }
    void bfs(int x,int y,int &res,vector<vector<char>>&grid,vector<vector<bool>>&f)
    {
        vector<vector<int>>dir{{1,0},{-1,0},{0,1},{0,-1}};
        queue<pair<int,int>>p;
        p.push({x,y});
        while(!p.empty())
        {
            pair<int,int>k=p.front();
            f[k.first][k.second]=true;
            p.pop();
            for(auto m:dir)
            {
                int xx=m[0]+k.first,yy=m[1]+k.second;
                if(check(xx,yy,grid,f))p.push({xx,yy});
            }
        }
        res++;
    }
    int solve(vector<vector<char> >& grid) {
        int res=0;
        vector<vector<bool>> f(grid.size()+10,vector<bool>(grid[0].size()+10,false));
        for(int i=0;i<grid.size();i++)
            for(int j=0;j<grid[0].size();j++)
                if(check(i,j,grid,f))bfs(i,j,res,grid,f);
        return res;
    }
};