[LintCode] 600 Smallest Rectangle Enclosing Black Pixels 解题报告

Description
An image is represented by a binary matrix with 0 as a white pixel and 1 as 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,
Return 6.

思路
题目中给了location(x, y)，并且说明所有的点都是connected。这就告诉了我们y的左边是先0后1的情况，或者没有1。而y的右边是先1后0的情况，也或者没有1。x往上看，或者往下看，也是相同的分析。
这样我们就可以想到用二分法来做了。
我们二分法四次分别找：
1：y（包括y）左边最靠左的1的位置
2：y（包括y）右边最靠右的1的位置
3：x（包括x）上面最靠上的1的位置
4：x（包括x）下面最靠下的1的位置

用这几个位置就可以算出长方形的大小。

Code

public class Solution {
    /**
     * @param image a binary matrix with '0' and '1'
     * @param x, y the location of one of the black pixels
     * @return an integer
     */
    public int minArea(char[][] image, int x, int y) {
        // Write your code here
        
        int N = image.length;
        if (N == 0) {
            return 0;
        }
        int M = image[0].length;
        if (M == 0) {
            return 0;
        }
        
        int start = 0;
        int end = y;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (checkColumn(image, mid)) {
                end = mid;
            }
            else {
                start = mid;
            }
        }
        
        int left = 0;
        if (checkColumn(image, start)) {
            left = start;
        }
        else if (checkColumn(image, end)) {
            left = end;
        }
        else {
            return 0;
        }
        
        start = y;
        end = M - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (checkColumn(image, mid)) {
                start = mid;
            }
            else {
                end = mid;
            }
        }
        
        int right = y;
        if (checkColumn(image, end)) {
            right = end;
        }
        else if (checkColumn(image, start)) {
            right = start;
        }
        
        start = 0;
        end = x;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (checkRow(image, mid)) {
                end = mid;
            }
            else {
                start = mid;
            }
        }
        
        int top = 0;
        if (checkRow(image, start)) {
            top = start;
        }
        else if (checkRow(image, end)) {
            top = end;
        }
        
        start = x;
        end = N - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (checkRow(image, mid)) {
                start = mid;
            }
            else {
                end = mid;
            }
        }
        
        int bottom = x;
        if (checkRow(image, end)) {
            bottom = end;
        }
        else if (checkRow(image, start)) {
            bottom = start;
        }
        
        return (right - left + 1) * (bottom - top + 1);

    }
    
    private boolean checkColumn(char[][] image, int col) {
        for (int i = 0; i < image.length; i++) {
            if (image[i][col] == '1') {
                return true;
            }
        }
        return false;
    }
    
    private boolean checkRow(char[][] image, int row) {
        for (int j = 0; j < image[0].length; j++) {
            if (image[row][j] == '1') {
                return true;
            }
        }
        return false;

    }
}

Solution 2:

public class Solution {
    /**
     * @param image a binary matrix with '0' and '1'
     * @param x, y the location of one of the black pixels
     * @return an integer
     */
    public int minArea(char[][] image, int x, int y) {
        // Write your code here
        int m = image.length;
        int n = image[0].length;
        
        int left = checkColumn(image, 0, y, 0, m, true);
        int right = checkColumn(image, y + 1, n, 0, m, false);
        int top = checkRow(image, left, right, 0, x, true);
        int bottom = checkRow(image, left, right, x + 1, m, false);
        
        return (right - left) * (bottom - top);
    }
    
    public int checkColumn(char[][] image, int i, int j, int top, int bottom, boolean goLeft) {
        while (i != j) {
            int k = top;
            int mid = i + (j - i) / 2;
            while (k < bottom && image[k][mid] == '0') {
                k++;
            }
            if (k < bottom == goLeft) {
                j = mid;
            }
            else {
                i = mid + 1;
            }
        }
        return i;
    }
    
    public int checkRow(char[][] image, int left, int right, int i, int j, boolean goUp) {
        while (i != j) {
            int k = left;
            int mid = i + (j - i) / 2;
            while (k < right && image[mid][k] == '0') {
                k++;
            }
            if (k < right == goUp) {
                j = mid;
            }
            else {
                i = mid + 1;
            }
        }
        return i;
    }
}