A review of all solutions


  • 0

    1.dfs

        int numIslands(vector<vector<char>>& grid) {
            int res=0;
            for(int i=0;i<grid.size();i++) for(int j=0;j<grid[0].size();j++) res+=dfs(i,j,grid);
            return res;
        }
        bool dfs(int r, int c, vector<vector<char>>& grid) {
            if(r<0 || r== grid.size() || c<0 || c== grid[0].size() || grid[r][c]=='0') return 0;
            grid[r][c]='0';
            char dir[]={-1,0,1,0,-1};
            for(int i=0; i<4; i++) dfs(r+dir[i],c+dir[i+1],grid);
            return 1;
        }
    
    1. bfs
        int numIslands(vector<vector<char>>& grid) {
            int res=0;
            for(int i=0;i<grid.size();i++) for(int j=0;j<grid[0].size();j++) res+=bfs(i,j,grid);
            return res;
        }
        bool bfs(int r, int c, vector<vector<char>>& grid) {
            if(grid[r][c]=='0') return 0;
            char dir[]={-1,0,1,0,-1};
            queue<pair<int,int>> q({pair<int,int>(r,c)});
            while(!q.empty()) {
                auto &p = q.front();
                q.pop();
                int x = p.first, y = p.second;
                if(x<0 || x== grid.size() || y<0 || y== grid[0].size() ||grid[x][y]=='0') continue;
                grid[x][y]='0';
                for(int i=0; i<4; i++) q.push(pair<int,int>(x+dir[i],y+dir[i+1]));
            }
            return 1;
        }
    
    1. union find
        int numIslands(vector<vector<char>>& grid) {
            if(grid.empty()) return 0;
            int r = grid.size(), c = grid[0].size(), count=r*c;
            vector<int> id(r*c);
            iota(id.begin(),id.end(),0);
            char dir[] = {-1,0,1,0,-1};
            for(int i=0;i<r;i++) 
                for(int j=0;j<c;j++) {
                    if(grid[i][j]=='0') {
                        count--;
                        continue;
                    }
                    int rt = root(i*c+j,id);
                    for(int k=0;k<4;k++) {
                        int x = i+dir[k], y = j+dir[k+1];
                        if(x<0||x==r||y<0||y==c||grid[x][y]=='0') continue;
                        int rtn = root(x*c+y,id);
                        if (rt != rtn) {
                            id[rtn] = rt;
                            count--;
                        }
                    }
                } 
            return count;
        }
        int root(int i, vector<int> &id) {
    	    while(id[i]!=i) i=id[i]=id[id[i]];
    	    return i;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.