मान लीजिए कि हमारे पास एक बाइनरी मैट्रिक्स है। हमें यह पता लगाना है कि क्या दिए गए मैट्रिक्स में कोई आयत या अनुक्रम है जिसके चारों कोने 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