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.
