> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/binarysearch/302.-smallest-rectangle-enclosing-black-pixels.md).

# 302. Smallest Rectangle Enclosing Black Pixels

零矩阵中由一坨以(x, y)为中心相连的1，让找出这坨1的四边边界。因为是相连的，拿上边界来说，从\[0, x]中某行开始往后都出现了1，那行就是上边界。因此二分法找第一个1出现的行，对每个候选mid行，遍历列检查是否由1存在。其余边界同理，上下边界找完后有1存在的行范围已固定，可以用此帮助缩小在找左右边界中行要检查的范围。

题目和答案参考自[这](https://link.zhihu.com/?target=https%3A//www.cnblogs.com/grandyang/p/5268775.html)。

```cpp
class Solution {
public:
    int minArea(vector<vector<char>>& image, int x, int y) {
        const int M = image.size(), N = image[0].size();
        // h: 遍历列还是行; i, j: 二分范围；low high: 检查有无1的范围；delta: 没查到1后往哪边动
        const auto bs = [&](bool h, int i, int j, int low, int high, int delta) {
            while (i < j) {
                int k = low, mid = i + (j - i) / 2;
                // 沿着一直搜索直到找到1
                while (k < high && (h ? image[mid][k] : image[k][mid]) == '0') ++k;
                // 是否遍历到了边界，到了意味着此行/列没有1
                if (k == high) i = mid + delta;
                else j = mid;
            }
            return i;
        };
        int up = bs(true, 0, x, 0, N, true, 1);
        int down = bs(true, x + 1, M, 0, N, -1);
        int left = bs(false, 0, y, up, down, 1);
        int right = bs(false, y + 1, N, up, down, -1);
    }
};

```