C++で2値行列に4つのコーナーがすべて1の長方形が存在するかを判定する方法

問題の概要

0と1のみで構成される2値行列が与えられたとします。この行列の中に、4つのコーナー（角）がすべて1である長方形が存在するかどうかを判定するのが、本記事のテーマです。

例として、次のような行列を考えてみましょう。

この行列の場合、答えは「はい」となります。実際に、コーナーがすべて1である長方形が存在します。

上の部分行列に注目すると、左上・右上・左下・右下の4つのコーナーがすべて1になっていることが確認できます。

解決のためのアプローチ

この問題を効率的に解くために、ハッシュセット（unordered_set）を活用した手法を採用します。アルゴリズムの流れは以下のとおりです。

• 行列を上から下へ、一行ずつ走査します。

• 各行において、値が1となる2つの列（j と k）の組み合わせをすべて調べ、そのペアをハッシュマップに記録します。

• それ以降の行で同じ列のペア（j と k が再び両方とも1）が見つかった場合、その4つの要素が長方形の4つのコーナーを形成していることになります。

同じ列ペアが2回以上出現した時点で長方形の存在が確定するため、無駄な探索を省き、効率的に判定できます。

C++による実装例

#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

計算量の目安

このアルゴリズムの時間計算量は O(行数 × 列数²) となります。これは、各行についてすべての列ペアを調べるためです。また、空間計算量は O(列数²) となり、記録する列ペアの数に依存します。行列のサイズが大きい場合でも、ハッシュを利用した高速な検索により、実用的な速度で動作します。