C++で回転・平行移動後の画像一致を判定するプログラム

2つの n × n ピクセルの正方形画像 first と second が与えられたとき、second を 90 度単位で回転および平行移動させて first と一致させられるかどうかを判定する C++ プログラムを解説します。画素は黒（'x'）と白（'.'）の 2 値で表現されます。

問題の概要

入力例:

n = 4
first  = {"..x.", "x.x.", "x.xx", "xx.."}
second = {"..xx", "x.xx", ".x.x", "..x."}

出力: false（0）

この例では、second をどう回転・平行移動しても first と一致しないため false が返されます。

アルゴリズムの考え方

1. 黒画素の座標を抽出: 各画像から黒画素（'x'）の座標 (行, 列) を配列 a, b に格納します。
2. 画素数のチェック: 黒画素の数が異なれば即座に false、両方 0 なら true を返します。
3. 基準点を揃えて比較: 配列をソートし、先頭要素同士を基準として相対位置（ベクトル）がすべて一致するかを確認します。これが平行移動の判定に相当します。
4. 4 回の回転を試す: second の座標配列 b を 90 度ずつ計 4 回回転させ、それぞれで上記の比較を行います。いずれかで一致すれば true。

座標の回転公式

n × n グリッド上で点 (r, c) を原点中心に 90 度時計回りに回転させると (c, n - 1 - r) になります。実装ではこの変換を b 配列の各要素に適用します。

C++ 実装例

#include <bits/stdc++.h>
using namespace std;

// 2 つの座標配列が同一の平行移動で一致するか判定
bool match(const vector<pair<int, int>>& base,
           const vector<pair<int, int>>& target) {
    if (base.empty()) return true;
    int dr = target[0].first  - base[0].first;
    int dc = target[0].second - base[0].second;
    for (size_t i = 1; i < base.size(); ++i) {
        if (target[i].first  - base[i].first  != dr ||
            target[i].second - base[i].second != dc) {
            return false;
        }
    }
    return true;
}

// 座標配列を 90 度時計回りに回転
void rotate90(int n, vector<pair<int, int>>& v) {
    for (auto& p : v) {
        p = {p.second, n - 1 - p.first};
    }
}

bool solve(int n, const vector<string>& first,
           const vector<string>& second) {
    vector<pair<int, int>> a, b;
    
    // 黒画素の座標を収集
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (first[i][j] == 'x') a.emplace_back(i, j);
            if (second[i][j] == 'x') b.emplace_back(i, j);
        }
    }
    
    if (a.size() != b.size()) return false;
    if (a.empty()) return true;
    
    sort(a.begin(), a.end());
    
    for (int rot = 0; rot < 4; ++rot) {
        sort(b.begin(), b.end());
        if (match(a, b)) return true;
        rotate90(n, b);
    }
    return false;
}

int main() {
    int n = 4;
    vector<string> first  = {"..x.", "x.x.", "x.xx", "xx.."};
    vector<string> second = {"..xx", "x.xx", ".x.x", "..x."};
    cout << boolalpha << solve(n, first, second) << endl; // false
    return 0;
}

計算量

• 時間計算量: O(n² + k log k) （k は黒画素の数、ソートが支配的）
• 空間計算量: O(k)

ポイント・注意点

• 座標配列をソートすることで、対応する画素同士をインデックスで合わせられるようにしています。
• 平行移動の判定は「基準点（先頭要素）からの相対ベクトルがすべて等しい」ことで行います。
• 元のコードの find 関数にはバグがありました（d2 計算で y[1] を使用）。修正版では y[0] で統一しています。
• 回転は b 側のみ行い、a は固定します。これにより実装がシンプルになります。

入力・出力例

入力:
4, {"..x.", "x.x.", "x.xx", "xx.."}, {"..xx", "x.xx", ".x.x", "..x."}

出力:
false