在C ++中查找二进制矩阵中是否存在一个角为1的矩形

假设我们有一个二进制矩阵。我们必须找出给定矩阵中是否有任何矩形或序列的所有四个角均等于1。

结果将是。这里有一个矩形，其角为1s。

为了解决这个问题，我们将使用一种有效的方法。我们将遵循以下步骤-

• 从上到下逐行扫描矩阵

• 对于每一行，请记住两个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