//dfs遍历，时间O(mn)，空间O(mn)。
//用O(mlogn + nlogm)的时间，O(1)的空间做出这道题，是利用投影和binary search的做法。
class Solution {
public:
    /**
     * @param image a binary matrix with '0' and '1'
     * @param x, y the location of one of the black pixels
     * @return an integer
     */
    int minArea(vector<vector<char>>& image, int x, int y) {
        // Write your code here
        int row = image.size();
        if (row == 0) {
            return 0;
        }
        int col = image[0].size();
        if (col == 0) {
            return 0;
        }

        int upperBound = findUpperBound(image, x);
        int lowerBound = findLowerBound(image, x, row - 1);
        int leftBound = findLeftBound(image, y);
        int rightBound = findRightBound(image, y, col - 1);
        /*
        cout << upperBound << endl;
        cout << lowerBound << endl;
        cout << leftBound << endl;
        cout << rightBound << endl;
        */
        return (lowerBound - upperBound + 1) * (rightBound - leftBound + 1);
    }

    int findUpperBound(vector<vector<char>>& image, int x) {
        int start = 0;
        int end = x;

        while (start + 1 < end) {
            int mid = (end - start) / 2 + start;
            if (rowHasNoBlackPixel(image, mid)) {
                start = mid;
            } else {
                end = mid;
            }
        }
        if (rowHasNoBlackPixel(image, start)) {
            return end;
        } else {
            return start;
        }
    }

    int findLowerBound(vector<vector<char>>& image, int x, int row) {
        int start = x;
        int end = row;

        while (start + 1 < end) {
            int mid = (end - start) / 2 + start;
            if (rowHasNoBlackPixel(image, mid)) {
                end = mid;
            } else {
                start = mid;
            }
        }

        if (rowHasNoBlackPixel(image, end)) {
            return start;
        } else {
            return end;
        }
    }

    int findLeftBound(vector<vector<char>>& image, int y) {
        int start = 0;
        int end = y;

        while (start + 1 < end) {
            int mid = (end - start) / 2 + start;
            if (colHasNoBlackPixel(image, mid)) {
                start = mid;
            } else {
                end = mid;
            }
        }

        if (colHasNoBlackPixel(image, start)) {
            return end;
        } else {
            return start;
        }
    }

    int findRightBound(vector<vector<char>>& image, int y, int col) {
        int start = y;
        int end = col;

        while (start + 1 < end) {
            int mid = (end - start) / 2 + start;
            if (colHasNoBlackPixel(image, mid)) {
                end = mid;
            } else {
                start = mid;
            }
        }

        if (colHasNoBlackPixel(image, end)) {
            return start;
        } else {
            return end;
        }
    }

    bool rowHasNoBlackPixel(vector<vector<char>>& image, int row) {
        for (int i = 0; i < image[row].size(); i++) {
            if (image[row][i] == '1') {
                return false;
            }
        }
        return true;
    }

    bool colHasNoBlackPixel(vector<vector<char>>& image, int col) {
        for (int i = 0; i < image.size(); i++) {
            if (image[i][col] == '1') {
                return false;
            }
        }
        return true;
    }
};