302. Smallest Rectangle Enclosin

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:

Input:
[
"0010",
"0110",
"0100"
]
and x = 0, y = 2

Output: 6

我的思路：DFS，但是其实和brute force区别不大

答案的第三种：binary search

class Solution {
public:
    int minArea(vector<vector<char>>& image, int x, int y) {
        int leftmost=0, rightmost=0, topmost=0, bottommost=0;
        
        int left=0, right=y, mid, row;
        while (left < right) {
            mid = (left + right)/2;
            for (row=0; row<image.size() and image[row][mid]!='1'; ++row);
            if (row == image.size())
                left = mid+1;
            else
                right = mid;
        }
        leftmost = left;
        
        
        left=y, right=image[0].size(); // left=y+1?
        while (left < right) {
            mid = (left + right)/2;
            for (row=0; row<image.size() and image[row][mid]!='1'; ++row);
            if (row == image.size())
                right = mid;
            else
                left = mid+1;
        }
        rightmost = left;
        
        
        int top=0, bottom=x, col;
        while (top < bottom) {
            mid = (top + bottom)/2;
            for (col=0; col<image[0].size() and image[mid][col]!='1'; ++col);
            if (col == image[0].size())
                top = mid+1;
            else
                bottom = mid;
        }
        topmost = top;
        
        
        top=x, bottom=image.size(); // top=x+1?
        while (top < bottom) {
            mid = (top + bottom)/2;
            for (col=0; col<image[0].size() and image[mid][col]!='1'; ++col);
            if (col == image[0].size())
                bottom = mid;
            else
                top = mid+1;
        }
        bottommost = top;
        
        return (rightmost-leftmost)*(bottommost-topmost);
    }
};

Runtime: 84 ms, faster than 65.52% of C++ online submissions for Smallest Rectangle Enclosing Black Pixels.
Memory Usage: 16.4 MB, less than 98.28% of C++ online submissions for Smallest Rectangle Enclosing Black Pixels.