Concise C++ DFS solution, 10ms, O(m*n) time, O(1) space.


  • 0
    F
    class Solution {
    public:
        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' || grid[i][j] == 'X') 
                return;
            grid[i][j] = 'X';
            dfs(grid, i+1, j);
            dfs(grid, i, j+1);
            dfs(grid, i-1, j);
            dfs(grid, i, j-1);
        }
        
        int numIslands(vector<vector<char>> &grid) {
            if(grid.empty() || grid[0].empty()) 
                return 0;
            int M = grid.size(), N = grid[0].size();
            
            int count=0;
            for(int i=0; i<M; ++i){
                for(int j=0; j<N; ++j){
                    if(grid[i][j]=='1'){
                        dfs(grid, i, j);
                        count++;
                    }    
                }
            }
            return count;
        }
    };

Log in to reply
 

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