C++で3×3パターンが中心対称かどうかを判定する方法

問題概要

「X」と「.」から構成される 3 × 3 の行列を考えます。このパターンが中心対称(点対称)であるかどうかを判定します。中心対称とは、図形の中心点を基準に 180 度回転させても元の形と完全に重なるような対称性のことです。

たとえば、次のような入力が与えられた場合を考えてみましょう。

この場合、出力は True(真)になります。各マスを中心に対して反転させると、すべての要素が一致するためです。

解法のステップ

この問題を解くには、以下の条件でチェックを行います。

M[0, 0] == M[2, 2] かつ
M[0, 1] == M[2, 1] かつ
M[0, 2] == M[2, 0] かつ
M[1, 0] == M[1, 2]
がすべて成り立てば true を返す
そうでなければ false を返す

ポイントは、中心の要素 M[1][1] は自分自身との比較になるため、チェックする必要がないという点です。したがって、対比すべきペアは外周の 8 マスだけで済みます。

実装例

理解を深めるために、以下の C++ 実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
bool solve(vector<vector<char>> M){
    if (M[0][0] == M[2][2] && M[0][1] == M[2][1] && M[0][2] == M[2][0] && M[1][0] == M[1][2])
        return true;
    else
        return false;
}
int main(){
    vector<vector<char>> matrix = { { 'X', 'X', '.' }, { '.', '.', '.' }, { '.', 'X', 'X' } };
    cout << solve(matrix) << endl;
}

入力

{ { 'X', 'X', '.' }, { '.', '.', '.' }, { '.', 'X', 'X' } }

出力

1

solve 関数は bool 値を返すため、true の場合は標準出力に 1 が表示されます。これは、与えられた行列が中心対称であることを示しています。計算量は行列サイズが固定のため O(1) となり、非常に効率的な判定方法です。