ধরুন আমাদের একটি বাইনারি ম্যাট্রিক্স আছে। প্রদত্ত ম্যাট্রিক্সে কোন আয়তক্ষেত্র বা ক্রম আছে কিনা তা আমাদের খুঁজে বের করতে হবে যার চারটি কোণই 1 এর সমান। ম্যাট্রিক্সটি এরকম
| 1 | 0 | 0 | 1 | ৷0 |
| 0 | 0 | 1 | ৷0 | 1 | ৷
| 0 | 0 | 0 | 1 | ৷0 |
| 1 | 0 | 1 | ৷0 | 1 | ৷
ফলাফল হ্যাঁ হবে। এখানে একটি আয়তক্ষেত্র রয়েছে, যার কোণগুলি 1s সহ।
| 1 | 0 | 1 | ৷
| 0 | 1 | ৷0 |
| 1 | 0 | 1 | ৷
এটি সমাধান করার জন্য আমরা একটি কার্যকর পদ্ধতি ব্যবহার করব। আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
লাইন দ্বারা উপরের থেকে নীচের লাইন পর্যন্ত ম্যাট্রিক্স স্ক্যান করুন
-
প্রতিটি লাইনের জন্য দুটি 1 এর প্রতিটি সংমিশ্রণ মনে রাখুন এবং এটি একটি হ্যাশ-সেটে পুশ করুন।
-
যদি আমরা পরবর্তী লাইনে আবার সেই সংমিশ্রণটি খুঁজে পাই, আমরা আমাদের আয়তক্ষেত্রটি পাব।
উদাহরণ
#include<iostream>
#include<unordered_set>
#include<unordered_map>
#include<vector>
using namespace std;
bool isRectanglePresent(const vector<vector<int> >& matrix) {
int rows = matrix.size();
if (rows == 0)
return false;
int columns = matrix[0].size();
unordered_map<int, unordered_set<int> > table;
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < columns - 1; ++j) {
for (int k = j + 1; k < columns; ++k) {
if (matrix[i][j] == 1 && matrix[i][k] == 1) {
if (table.find(j) != table.end() && table[j].find(k) != table[j].end())
return true;
if (table.find(k) != table.end() && table[k].find(j) != table[k].end())
return true;
table[j].insert(k);
table[k].insert(j);
}
}
}
}
return false;
}
int main() {
vector<vector<int> > matrix = {
{ 1, 0, 0, 1, 0 },
{ 0, 0, 1, 0, 1 },
{ 0, 0, 0, 1, 0 },
{ 1, 0, 1, 0, 1 }
};
if (isRectanglePresent(matrix))
cout << "Rectangle is present";
else
cout << "Rectangle is not present";
} আউটপুট
Rectangle is present
