Easy Java DFS solution


  • 0
    B
    public class Solution {
        public int numIslands(char[][] grid) {
            //require
            int m=grid.length;
            if(m<1)return 0;
            int n=grid[0].length;
            int ans=0;
            //invariant
            for(int i=0;i<m;i++)
                for(int j=0;j<n;j++)
                    if(dfs(i,j,grid))ans++;
            //ensure
            return ans;
        }
        private boolean dfs(int i,int j,char[][] grid){
            int m=grid.length,n=grid[0].length;
            //base case
            if(i<0||i>=m||j<0||j>=n||grid[i][j]=='0')
                return false;
    
            //mark this point
            grid[i][j]='0';
            //infect the adjacent area
            dfs(i-1,j,grid);
            dfs(i+1,j,grid);
            dfs(i,j-1,grid);
            dfs(i,j+1,grid);
            return true;
        }
    }
    

Log in to reply
 

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