My accepted c++ solution (may be trivial)


  • 13
    S
    class Solution {
    public:
        void contaminate(vector<vector<char> > &grid, int i, int j){
            if(i>0&&grid[i-1][j]=='1'){
                grid[i-1][j]='0';
                contaminate(grid, i-1, j);
            }
            if(j>0&&grid[i][j-1]=='1'){
                grid[i][j-1]='0';
                contaminate(grid, i, j-1);
            }
            if(i<grid.size()-1&&grid[i+1][j]=='1'){
                grid[i+1][j]='0';
                contaminate(grid, i+1, j);
            }
            if(j<grid[0].size()-1&&grid[i][j+1]=='1'){
                grid[i][j+1]='0';
                contaminate(grid, i, j+1);
            }
        }
        int numIslands(vector<vector<char>> &grid) {
            int n=grid.size();
            if(n==0) return 0;
            int m=grid[0].size();
            
            int cnt=0;
            for(int i=0; i<n; i++){
                for(int j=0; j<m; j++){
                    if(grid[i][j]=='1'){
                        cnt++;
                        contaminate(grid, i, j);
                    }
                }
            }
            return cnt;
        }
    };

  • 0
    E

    does this DFS?


  • 0
    G

    Share my code, kinda like disjoint-set ,but no searching function is needed

    class Solution {
    public:
        int numIslands(vector<vector<char> >& grid) {
            if (grid.empty()) return 0;
            int row = grid.size(), col = grid[0].size();
            int n = row*col;
            int *father = new int[n];
            int res = 0;
         
            memset(father,-1,n*sizeof(int));
            
            
            for (int i=0;i<row;i++)
                for (int j=0;j<col;j++){
                    if (grid[i][j]=='1') { 
                        if (i==0&&j==0){ father[0]=0;continue;}
                        if (i==0)
                            father[j] = grid[0][j-1]=='1'?father[j-1]:j;
                        else if (j==0)
                            father[i*col] = grid[i-1][0]=='1'?father[(i-1)*col]:(i*col);
                        else{
                            int temp = col*i+j;
                            int fup = father[temp-col];
                            int fleft = father[temp-1];
                            
                            if (fup==-1&&fleft==-1)
                                father[temp] = temp;
                            else if (fup==-1&&fleft!=-1)
                                father[temp] = fleft;
                            else if (fup!=-1&&fleft==-1)
                                father[temp] = fup;
                            else{
                                if (fup!=fleft) father[max(fup,fleft)] = min(fup,fleft);
                                father[temp] = min(fup,fleft);
                            }
                        }
                    }
                }
                    
            for (int i=0;i<n;i++)
                if (father[i]==i)
                    res++;
                   
                    
            
            
                
            
            delete[] father;
           
            return res;
        }
    }; 

  • 0

    Nice recursion in contaminate.


  • 0
    R

    your idea is to make an island disappear once find one, right?


  • 0
    R

    can you say the complexity please?


  • 4
    T

    Same idea, but more concise code:

     void DFS(vector<vector<char>>& grid, int i, int j){
    	    if(i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size()) return;
    	    if('0' == grid[i][j]) return;
    	    grid[i][j] = '0';
    	    DFS(grid, i-1, j);
    	    DFS(grid, i+1, j);
    	    DFS(grid, i, j - 1);
    	    DFS(grid, i, j + 1);
    	}
    	int numIslands(vector<vector<char>>& grid) {
    		int counter = 0;
    		for (int i = 0; i < grid.size(); ++i)
    			for (int j = 0; j < grid[i].size(); ++j)
    				if ('1' == grid[i][j])
    				{
    					++counter;
    					DFS(grid, i, j);
    				}
    		return counter;
    	}

  • 0
    Y

    Maybe the code can be more clear:

    class Solution 
    {
    public:
        int numIslands(vector<vector<char>>& grid) 
        {
            if(grid.empty())
                return 0;
            const int m=grid.size();
            const int n=grid[0].size();
            int cnt=0;
            for(int i=0;i<m;++i)
            {
                for(int j=0;j<n;++j)
                {
                    if(dfsDetector(i,j,m,n,grid))
                      ++cnt;  
                }
            }
            return cnt;
        }
    private:
        bool dfsDetector(int i,int j,const int &m,const int &n,vector<vector<char>> &grid)
        {
            const static vector<vector<int>> dir={{0,1},{0,-1},{1,0},{-1,0}};
            const int dirCnt=dir.size();
            if(i<0 || i>=m || j<0 || j>=n)
                return false;
            if(grid[i][j]=='1')
            {
                grid[i][j]='2';
                for(int k=0;k<dirCnt;++k)
                    dfsDetector(i+dir[k][0],j+dir[k][1],m,n,grid);
                return true;
            }
            else
                return false;
        }
    };

  • 0
    J

    same idea, less cod and more clean

    int numIslands(vector<vector<char>>& grid) {
        const int row = grid.size();
        if (row == 0) return 0;
        const int col = grid[0].size();
        int cnt = 0;
        for (int i = 0; i < row; ++i)
         for (int j = 0; j < col; ++j) {
             if (grid[i][j] == '1') {
                 cnt++;
                 dfs(grid, i, j);
             }
         }
         return cnt;
    }
    void dfs(vector<vector<char>> &grid, int i, int j) {
        if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size() || grid[i][j] == '0') return;
        vector<pair<int, int>> dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        grid[i][j] = '0';
        for (auto dir : dirs) {
            dfs(grid, i+ dir.first, j + dir.second);
        }
    }

  • 0
    T

    O(nm): n*m for the initial calls to contaminate and the contaminate recursive calls will collectively clear all '1's which cannot be no more than n*m.


  • 0
    T

    I think you should declare that dirs static (or outside the function) as it will be recreated on every dfs call, that is row*col times at worst.


  • 0
    This post is deleted!

  • 0
    A

    Nice idea, but I think the interviewer is going to ask you to avoid updating the original grid.


  • 0
    S

    @animageofmine Do you mean the parameter is "const vector<vector<char>>& grid"?In that case,we can construct a new array whose type is bool[][] or deque<deque<bool>> to record the gird we have traversed.


  • 0
    M

    @tju_xu97 - don't we need {} braces with for loop? How does your code work without the braces?


Log in to reply
 

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