मान लीजिए हमारे पास एक छवि है और वह छवि एक बाइनरी मैट्रिक्स द्वारा दर्शाई गई है जिसमें 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, left, right, one लेगा,
जब तक i < j, करें −
mid := i + (j - i) / 2
k := left
जब तक (k < right और v[mid, k] '0' के समान है), करें −
(k को 1 से बढ़ाएं)
यदि 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 को 1 से बढ़ाएं)
यदि k < bottom, one के समान है, तो −
j := mid
अन्यथा
i := mid + 1
i लौटाएं
मुख्य विधि से निम्नलिखित करें −
v := image
ret := 0
n := image का पंक्ति आकार
m := image का स्तंभ आकार
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 < 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आउटपुट
6
