C++でコーナーが1の2値行列に長方形があるかどうかを調べます

バイナリ行列があるとします。与えられた行列に、四隅すべてが1に等しい長方形またはシーケンスがあるかどうかを確認する必要があります。行列は次のようになります

結果はyesになります。ここに1つの長方形があり、その角は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