题解 | #岛屿数量#

注意细节问题。

class Solution {
public:
    /**
     * 判断岛屿数量
     * @param grid char字符型vector<vector<>> 
     * @return int整型
     */
    int solve(vector<vector<char> >& grid) {
        // write code here

        int res=0;
        vector<vector<int>> visit;

        for(int i =0 ; i < grid.size(); i++){
            visit.push_back(vector<int> ());
            for(int j = 0; j<grid[0].size();j++){
                visit[i].push_back(0);
            }
        }

        for(int i =0 ; i < grid.size(); i++){
            for(int j = 0; j<grid[0].size();j++){
                if(!visit[i][j]&&grid[i][j]=='1'){
                    BFS(grid,visit,i,j);
                    res++;
                }
            }
        }

        return res;
    }

    void BFS(vector<vector<char> >& grid, vector<vector<int> >& visits,int x, int y){
        const static int dx[] = {-1,1,0,0};
        const static int dy[] = {0,0,-1,1};
        queue<pair<int,int>> Q;

        Q.push({x,y});
        visits[x][y] = 1;

        while(!Q.empty()){

            int x =  Q.front().first;
            int y =  Q.front().second;
            Q.pop();

            for(int i = 0;i<4;i++){

                int newx = x + dx[i];
                int newy = y + dy[i];

                if(newx<0||newx>=visits.size()
                   ||newy<0||newy>=visits[0].size())
                   continue;

                if(!visits[newx][newy]&&grid[newx][newy]=='1'){
                    Q.push({newx,newy});
                    visits[newx][newy] = 1;
                }

            }
        }


    }

};