leetcode codes april contest

number of islands.cpp

/*Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.*/


class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int r=grid.size();
        if(r==0) return 0;
        int c=grid[0].size();
        bool vis[r][c];
        for(int i=0;i<r;++i) for(int j=0;j<c;++j) vis[i][j]=0;
        int cp=0;
        for(int i=0;i<r;++i){
            for(int j=0;j<c;++j){
                if(grid[i][j]=='1' && !vis[i][j]){
                    ++cp;
                    queue<pair<int,int>> q;
                    q.push({i,j});
                    vis[i][j]=1;
                    while(!q.empty()){
                        pair<int,int> pp=q.front();
                        q.pop();
                        int ii=pp.first;
                        int jj=pp.second;
                        // left
                        if(jj>=1 && grid[ii][jj-1]=='1' && !vis[ii][jj-1]){
                            vis[ii][jj-1]=1;
                            q.push({ii,jj-1});
                        }
                        // top
                        if(ii>=1 && grid[ii-1][jj]=='1' && !vis[ii-1][jj]){
                            vis[ii-1][jj]=1;
                            q.push({ii-1,jj});
                        }
                        // right
                        if((jj+1)<c && grid[ii][jj+1]=='1' && !vis[ii][jj+1]){
                            vis[ii][jj+1]=1;
                            q.push({ii,jj+1});
                        }
                        // bottom
                        if((ii+1)<r && grid[ii+1][jj]=='1' && !vis[ii+1][jj]){
                            vis[ii+1][jj]=1;
                            q.push({ii+1,jj});
                        }
                    }
                }
            }
        }
        return cp;
    }
};