C++ में बाइनरी मैट्रिक्स में कोनों पर 1 वाला आयत ढूंढें

मान लीजिए हमारे पास एक बाइनरी मैट्रिक्स है। हमें उस मैट्रिक्स में किसी आयत या अनुक्रम को ढूंढना है जिसके चारों कोने 1 के बराबर हैं। मैट्रिक्स इस तरह है

परिणाम हाँ होगा। यहां एक आयत मौजूद है, जिसके कोने 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