Tìm xem có một hình chữ nhật trong ma trận nhị phân với các góc là 1 trong C ++

Giả sử chúng ta có một ma trận nhị phân. Chúng ta phải tìm xem có hình chữ nhật hoặc dãy nào trong ma trận đã cho mà cả bốn góc đều bằng 1. Ma trận giống như

Kết quả sẽ là có. Đây là một hình chữ nhật có các góc bằng 1s.

Để giải quyết vấn đề này, chúng tôi sẽ sử dụng một cách tiếp cận hiệu quả. Chúng tôi sẽ làm theo các bước sau -

• Quét ma trận từ trên xuống dưới từng dòng

• Đối với mỗi dòng, hãy nhớ từng kết hợp của hai chữ 1 và đẩy nó vào một bộ băm.

• Nếu chúng ta tìm thấy lại sự kết hợp đó ở dòng sau, chúng ta sẽ có được hình chữ nhật của mình.

Ví dụ

#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";
}

Đầu ra

Rectangle is present