C++-এ কালো পিক্সেল ঘেরানোর সর্বনিম্ন রেক্ট্যাঙ্গেল (Smallest Rectangle Enclosing Black Pixels)

ধরি আমাদের একটি ছবি আছে যা বাইনারি ম্যাট্রিক্স দিয়ে প্রতিনিধিত্ব করা হয়েছে: 0 = সাদা পিক্সেল, 1 = কালো পিক্সেল। কালো পিক্সেলগুলো সংযুক্ত (connected), অর্থাৎ শুধু একটি কালো অঞ্চল আছে। পিক্সেলগুলো হরিজেন্টালি এবং ভার্টিক্যালি সংযুক্ত। যদি একটি কালো পিক্সেলের লোকেশন (x, y) দেওয়া থাকে, তবে সব কালো পিক্সেল ঘেরানোর সর্বনিম্ন (অ্যাক্সিস-আলাইনড) রেক্ট্যাঙ্গেলের এলাকা বের করতে হবে।

উদাহরণস্বরূপ, ইনপুট:

0	0	1	0
0	1	1	0
0	1	0	0

x = 0, y = 2 হলে আউটপুট হবে 6।

সমাধানের ধাপসমূহ

একটি 2D অ্যারে v সংজ্ঞায়িত।
searchRows(i, j, left, right, one) ফাংশন:
- যখন i < j:
  - mid := i + (j-i)/2
  - k := left
  - যখন k < right এবং v[mid][k] == '0': k++
  - যদি (k < right) == one: j := mid, অন্যথায় i := mid+1
- i ফেরত।
searchColumn(i, j, top, bottom, one) ফাংশন:
- যখন i != j:
  - mid := i + (j-i)/2
  - k := top
  - যখন k < bottom এবং v[k][mid] == '0': k++
  - যদি (k < bottom) == one: j := mid, অন্যথায় i := mid+1
- i ফেরত।
মেইন মেথড:
- v := image
- n := image.size(), m := image[0].size()
- top := searchRows(0, x, 0, m, true)
- bottom := searchRows(x+1, n, 0, m, false)
- left := searchColumn(0, y, top, bottom, true)
- right := searchColumn(y+1, m, top, bottom, false)
- ফেরত: (right - left) * (bottom - top)

প্রোগ্রাম উদাহরণ

#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();
        int 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));
}

ইনপুট

{{'0','0','1','0'},{'0','1','1','0'},{'0','1','0','0'}}, 0, 2