Simple C++ Clean recursive solution DFS 9ms


  • 0
    A
    int dr[] = {0 , 0 , -1 , 1} ; 
    int dc[] =  {1,  -1 , 0 , 0} ;
    
    
    class Solution {
    public:
        
        int r , c;
        vector<vector<int> > marked;
        inline void dfs(int curr_r, int curr_c ,vector<vector<char>>& grid ){
            marked[curr_r][curr_c] = 1;
            for(int i = 0 ; i<4 ; i++){
                if(curr_r+dr[i]<r and curr_r+dr[i]>=0 and curr_c+dc[i]<c and curr_c+dc[i]>=0){
                    if(!marked[curr_r+dr[i]][curr_c+dc[i]] and grid[curr_r+dr[i]][curr_c+dc[i]] == '1')
                        dfs(curr_r+dr[i] , curr_c+dc[i],grid );
                }
            }
        }
        int numIslands(vector<vector<char>>& grid) {
            r = grid.size() ; 
            if(r==0)
                return 0;
            c = grid[0].size();
            marked.resize(r,vector<int>(c,0));
            int ans =  0 ;  
            for(int i = 0 ; i < r  ; i++){
                for(int j = 0 ; j < c ;  j++){
                    if(!marked[i][j] and grid[i][j] == '1'){
                        ans++;
                        dfs(i,j,grid);
                    }
                }
            }
            return ans;    
        }
    };
    

Log in to reply
 

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