Hình chữ nhật nhỏ nhất bao quanh pixel đen trong C++

Cho ảnh nhị phân (0 = trắng, 1 = đen). Các pixel đen liên kết thành một vùng (liên thông 4 hướng). Cho tọa độ (x, y) của một pixel đen, tìm diện tích hình chữ nhật nhỏ nhất (trục tọa độ) bao quanh tất cả pixel đen.

Ví dụ:

x = 0, y = 2 → Kết quả = 6

Phương pháp giải

Sử dụng tìm kiếm nhị phân để tìm 4 biên: top, bottom, left, right. searchRows() tìm hàng đầu/cuối có pixel đen trong khoảng cột [left, right). searchColumn() tìm cột đầu/cuối có pixel đen trong khoảng hàng [top, bottom). Độ phức tạp O(m log n + n log m).

Ví dụ chương trình

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector> v;
    
    int searchRows(int i, int j, int left, int right, bool one) {
        while (i < j) {
            int mid = i + (j - i) / 2;
            int k = left;
            while (k < right && v[mid][k] == '0') k++;
            if (k < right == one) j = mid;
            else i = mid + 1;
        }
        return i;
    }
    
    int searchColumn(int i, int j, int top, int bottom, bool one) {
        while (i != j) {
            int mid = i + (j - i) / 2;
            int k = top;
            while (k < bottom && v[k][mid] == '0') k++;
            if (k < bottom == one) j = mid;
            else i = mid + 1;
        }
        return i;
    }
    
    int minArea(vector>& image, int x, int y) {
        v = image;
        int n = image.size(), m = image[0].size();
        int top = searchRows(0, x, 0, m, true);
        int bottom = searchRows(x + 1, n, 0, m, false);
        int left = searchColumn(0, y, top, bottom, true);
        int right = searchColumn(y + 1, m, top, bottom, false);
        return (right - left) * (bottom - top);
    }
};

int main() {
    Solution ob;
    vector> v = {{'0','0','1','0'}, {'0','1','1','0'}, {'0','1','0','0'}};
    cout << ob.minArea(v, 0, 2);
    return 0;
}

Đầu vào

Ma trận 3x4, x=0, y=2

Đầu ra

6