C++ তে কালো পিক্সেলকে ঘিরে থাকা ক্ষুদ্রতম আয়তক্ষেত্র

ধরুন আমাদের একটি ইমেজ আছে এবং সেই ইমেজটিকে একটি বাইনারি ম্যাট্রিক্স দ্বারা 0 একটি সাদা পিক্সেল এবং 1টি একটি কালো পিক্সেল হিসাবে উপস্থাপন করা হয়েছে। এখানে কালো পিক্সেল সংযুক্ত আছে, তাই শুধুমাত্র একটি কালো অঞ্চল আছে। পিক্সেলগুলি অনুভূমিকভাবে এবং উল্লম্বভাবে সংযুক্ত থাকে। যদি আমাদের একটি কালো পিক্সেলের একটি অবস্থান (x, y) থাকে, তাহলে আমাদের ক্ষুদ্রতম (অক্ষ-সারিবদ্ধ) আয়তক্ষেত্রের ক্ষেত্রফল খুঁজে বের করতে হবে যা সমস্ত কালো পিক্সেলকে ঘেরাও করে।

সুতরাং, যদি ইনপুট মত হয়

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

এবং x =0, y =2, তাহলে আউটপুট হবে 6

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

একটি 2D অ্যারে v
সংজ্ঞায়িত করুন
একটি ফাংশন searchRows() সংজ্ঞায়িত করুন, এটি i, j, বাম, ডান, এক,
যখন আমি করি
- মধ্য :=i + (j - i) / 2
- k :=বাম
- যখন (k <ডান এবং v[মিড, k] '0' এর মত একই), −
  করুন
  - (k 1 দ্বারা বাড়ান)
- যদি k <' ডান একের সমান হয়, তাহলে −
  - j :=মধ্য
- অন্যথায়
  - i :=মধ্য + 1
ফেরত i
একটি ফাংশন searchColumn() সংজ্ঞায়িত করুন, এটি i, j, টপ, বটম, ওয়ান,
আমি j এর সমান না হলেও −
কর
- মধ্য :=i + (j - i) / 2
- k :=শীর্ষ
- যখন (k <নীচে এবং v[k, mid] '0' এর মতো একই, −
  করুন
  - (k 1 দ্বারা বাড়ান)
- যদি k <নীচের অংশ একের মত হয়, তাহলে −
  - j :=মধ্য
- অন্যথায়
  - i :=মধ্য + 1
ফেরত i
প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -
v :=ছবি
ret :=0
n :=ছবির সারির আকার
m :=ছবির আকার
শীর্ষ :=অনুসন্ধান সারি (0, x, 0, মি, সত্য)
নিচে :=searchRows(x + 1, n, 0, m, false)
বাম :=অনুসন্ধান কলাম(0, y, শীর্ষ, নীচে, সত্য)
ডান :=অনুসন্ধান কলাম (y + 1, m, শীর্ষ, নীচে, মিথ্যা)
প্রত্যাবর্তন (ডান - বাম) * (নীচে - উপরে)

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   vector < vector <char> > 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<vector<char>>& image, int x, int y) {
      v = image;
      int ret = 0;
      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);
   }
};
main(){
   Solution ob;
   vector<vector<char>> 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