AC DFS JAVA Solution


  • 0
    U
    public int minArea(char[][] image, int x, int y) {
        boolean[][] visited= new boolean[image.length][image[0].length];
        HashMap<Integer, Integer> map = new HashMap<Integer,Integer>();
        map.put(0,x);// x min;
        map.put(1,x);// x max
        map.put(2,y);// y min
        map.put(3,y);// y max;
        helper(image, x, y, visited, map);
        
        return (map.get(1)-map.get(0)+1)*(map.get(3)-map.get(2)+1);// dont forget+1(2-0+1)*(2-1+1);
        
        
        
    }
    private void helper(char[][] image, int x, int y, boolean[][] visited,HashMap<Integer, Integer> map ){
        if(visited[x][y]||image[x][y]=='0')
            return;
        visited[x][y]=true;
        //update xmin xmax ymin, ymax;
        if(x<map.get(0))
            map.put(0,x);
        if(x>map.get(1))
            map.put(1,x);
        if(y<map.get(2))
            map.put(2,y);
        if(y>map.get(3))
            map.put(3,y);
        //dfs    
        if(x+1<image.length)
            helper(image, x+1, y, visited, map);
        if(x-1>=0)
            helper(image, x-1, y, visited, map);
        if(y+1<image[0].length)
            helper(image, x, y+1, visited, map);
        if(y-1>=0)
            helper(image, x, y-1, visited, map);
            
        
    }

Log in to reply
 

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