600.Smallest Rectangle Enclosing Black Pixels

1.Description(Hard)

An image is represented by a binary matrix with0as a white pixel and1as a black pixel. The black pixels are connected, i.e., there is only one black region. Pixels are connected horizontally and vertically. Given the location(x, y)of one of the black pixels, return the area of the smallest (axis-aligned) rectangle that encloses all black pixels.

Example

For example, given the following image:

[
  "0010",
  "0110",
  "0100"
]

and x =0, y =2, Return6.

2.Code

http://www.cnblogs.com/grandyang/p/5268775.html

Version 1: Binary Search

根据已有的black pixel的左边，分别找到上下左右含有1的边界，利用binary search查找。

 public int minArea(char[][] image, int x, int y) {
        if (image == null || image.length == 0 || image[0].length == 0) {
            return 0;
        }
        int m=image.length;
        int n=image[0].length;

        int top=searchtop(image,0,x);
        int bottom=searchbottom(image,x,m-1);
        int left=searchleft(image,0,y);
        int right=searchright(image,y,n-1);
        int area=(bottom-top+1)*(right-left+1);
        return area;
    }

    public int searchtop(char[][] image,int start,int end){

        while(start+1<end){
            int mid=start+(end-start)/2;
            if(isEmptyRow(image,mid)){
                start=mid;
            }
            else {
                end=mid;
            }
        }
        if(isEmptyRow(image,start)){
            return end;
        }
        return start;
    }
    public int searchbottom(char[][] image,int start,int end){
        while(start+1<end){
            int mid=start+(end-start)/2;
            if(isEmptyRow(image,mid)){
                end=mid;
            }
            else{
                start=mid;
            }
        }
        if(isEmptyRow(image,end)){
            return start;
        }
        return end;

    }
    public int searchleft(char[][] image,int start,int end){
        while(start+1<end){
            int mid=start+(end-start)/2;
            if(isEmptyColumn(image,mid)){
                start=mid;
            }
            else{
                end=mid;
            }
        }
        if(isEmptyColumn(image,start)){
            return end;
        }
        return start;
    }
    public int searchright(char[][] image,int start,int end){
        while(start+1<end){
            int mid=start+(end-start)/2;
            if(isEmptyColumn(image,mid)){
                end=mid;
            }
            else{
                start=mid;
            }
        }
        if(isEmptyColumn(image,end)){
            return start;
        }
        return end;
    }

    //find whether this column has '1'
    public boolean isEmptyColumn(char[][] image,int col){
        for(int i=0;i<image.length;i++){
            if(image[i][col]=='1'){
                return false;
            }
        }
        return true;
    }

    //find whether this row has '1'
    public boolean isEmptyRow(char[][] image,int row){
        for(int i=0;i<image[0].length;i++){
            if(image[row][i]=='1'){
                return false;
            }
        }
        return true;
    }

Version 2: Brute Force

这种方法的效率不高，遍历了整个数组，如果遇到了1，就更新矩形的返回

//Version 2:Brute force
public int minArea2(char[][] image, int x, int y){
    int up=x;
    int down=x;
    int left=y;
    int right=y;
    for(int i=0;i<image.length;i++){
        for(int j=0;j<image[0].length;j++){
            if(image[i][j]=='1'){
                up=Math.max(up, i);
                down=Math.min(down, i);
                left=Math.min(left,j);
                right=Math.max(right, j);
            }
        }
    }
    int area=(up-down+1)*(right-left+1);
    return area;
}