302

class Solution {
public:
    int minArea(vector<vector<char>>& image, int x, int y) {
        int rows = image.size(), cols = image[0].size();
        int left = searchCol(image, 0, y, 0, rows, true);
        int right = searchCol(image, y+1, cols, 0, rows, false);
        int top = searchRow(image, 0, x, left, right, true);
        int bottom = searchRow(image, x+1, rows, left, right, false);
        cout<<left<<" "<<right<<" "<<top<<" "<<bottom<<endl;
        return (right-left) * (bottom-top);
    }

    int searchCol(vector<vector<char>>& image, int l, int r, int start, int end, bool whiteToBlack){
        while(l<r){
            int mid = (l+r)/2, tmp = start;
            while(tmp < end && image[tmp][mid] == '0') tmp++;
            if(tmp < end == whiteToBlack)
                r = mid;
            else
                l = mid+1;
        }
        return l;
    }

    int searchRow(vector<vector<char>>& image, int l, int r, int start, int end, bool whiteToBlack){
        while(l<r){
            int mid = (l+r)/2, tmp = start;
            while(tmp < end && image[mid][tmp] == '0') tmp++;
            if(tmp < end == whiteToBlack)
                r = mid;
            else
                l = mid+1;
        }
        return l;
    }

};