Smallest Rectangle Enclosing Black Pixels

LintCode LeetCode

My first hard problem in LintCode：

这道题是一个用0代表white, 1代表black的棋盘，black是联通的，也就是说整个棋盘只有一个black 区域。给出一份black pixel的坐标（x,y),要返回能够覆盖掉所有black pixels的最小矩形的面积。

这道题我们要依次求出左右上下边界，再计算矩形面积。比如求左边界findLeft(),首先要从y列开始判断是否是全为white的WhiteCol，依次向左，直到找到最靠近y列的那一列全白的列，就是我们要找的左边届。

按照同样的方法找完上下左右边界后，计算面积不能凭直觉地采用 （下边界 - 上边界） * （右边界 - 左边界）， 通过画图可以轻易得出面积应该是（ 上边界 - 下边界 + 1） * （ 右边界 - 左边界 + 1）。

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
        if (image == null || image.length == 0 || image[0].length == 0){
            return 0;
        }
        int leftBound;
        int rightBound;
        int upperBound;
        int lowerBound;
        leftBound = findLeft(image,x,y);
        rightBound = findRight(image,x,y);
        upperBound = findUp(image,x,y);
        lowerBound = findLow(image,x,y);
        return (rightBound - leftBound + 1) * (lowerBound - upperBound + 1);
    }
        public int findLeft(char[][] image, int x, int y){
            int start = 0;
            int end = y;
            while (start + 1 < end){
                int mid = start + (end - start) / 2;
                if (isWhiteCol(mid,image)){
                    start = mid;
                } else {
                    end = mid;
                }
            }
            if (isWhiteCol(end,image)){
                return end + 1;
            } else if (isWhiteCol(start,image)){
                return start + 1;
            }
            return 0;
        }
        public int findRight(char[][] image, int x, int y){
            int start = y;
            int end = image[0].length - 1;
            while (start + 1 < end){
                int mid = start + (end - start) / 2;
                if (isWhiteCol(mid,image)){
                    end = mid;
                } else {
                    start = mid;
                }
            }
            if (isWhiteCol(start,image)){
                return start - 1;
            } else if (isWhiteCol(end,image)){
                return end - 1;
            }
            return image[0].length - 1;
        }
        public int findUp(char[][] image, int x, int y){
            int start = 0;
            int end = x;
            while (start + 1 < end){
                int mid = start + (end - start) / 2;
                if (isWhiteRow(mid,image)){
                    start = mid;
                } else {
                    end = mid;
                }
            }
            if (isWhiteRow(end,image)){
                return end + 1;
            } else if (isWhiteRow(start,image)){
                return start + 1;
            }
            return 0;
        }
        public int findLow(char[][] image, int x, int y){
            int start = x;
            int end = image.length - 1;
            while (start + 1 < end){
                int mid = start + (end - start) / 2;
                if (isWhiteRow(mid,image)){
                    end = mid;
                } else {
                    start = mid;
                }
            }
            if (isWhiteRow(start,image)){
                return start - 1;
            } else if (isWhiteRow(end,image)){
                return end - 1;
            } else {
                return image.length - 1;
            }
        }
        private boolean isWhiteRow(int row, char [][] image){
            for (int i = 0; i < image[0].length; i++){
                if (image[row][i] == '1'){
                    return false;
                }
            }
            return true;
        }
        private boolean isWhiteCol(int col, char [][] image){
            for (int i = 0; i < image.length; i++){
                if (image[i][col] == '1'){
                    return false;
                }
            }
            return true;
        }
}