C++에서 모서리가 1인 이진 행렬에 직사각형이 있는지 찾기

이진 행렬이 있다고 가정합니다. 주어진 행렬에 네 모서리가 모두 1인 직사각형이나 시퀀스가 ​​있는지 찾아야 합니다. 행렬은 다음과 같습니다.

결과는 예일 것입니다. 여기에 모서리가 1인 직사각형이 하나 있습니다.

이 문제를 해결하기 위해 하나의 효율적인 접근 방식을 사용합니다. 우리는 다음 단계를 따를 것입니다 -

• 행렬을 위에서 아래로 한 줄씩 스캔합니다.

• 각 행에 대해 2개의 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