C++で行列内の正方形の最大辺の長さを求めるアルゴリズム

この問題では、サイズ n × n の2次元行列 mat[][] が与えられます（n は奇数）。求めるのは、行列と同じ中心を持ち、外周の値がすべて等しい正方形の最大の辺の長さです。

問題の概要

与えられた行列の中から、行列の中心を共有する正方形の部分行列を探し、その外周（周囲）を構成する要素がすべて同じ値である場合に、その正方形の辺の長さを返します。条件を満たす複数の正方形がある場合は、最も大きいものを選びます。

入力例

mat[][] = {
    {2, 4, 6, 6, 5},
    {1, 7, 7, 7, 3},
    {5, 7, 0, 7, 1},
    {3, 7, 7, 7, 1},
    {2, 0, 1, 3, 2}
}

出力例

3

この例では、中心 (2, 2) を共有するサイズ 3×3 の部分行列があり、その外周はすべて「7」で構成されているため、答えは 3 となります。

解法のアプローチ

シンプルな解き方は次の通りです。まず、行列のサイズが奇数であるため、中心要素は必ずインデックス (n/2, n/2) の位置に存在します。中心を見つけたら、その周囲にある各サイズの部分行列（同心正方形）を順に調べ、外周の要素がすべて同じ値かどうかを確認します。

具体的には、中心から距離 i だけ離れた部分行列について、行 (n/2 - i) と (n/2 + i)、および列 (n/2 - i) と (n/2 + i) に含まれる要素が外周を形成します。i を 0 から n/2 まで変化させながら、外周の全要素が同一の値を持つかどうかをチェックしていきます。

アルゴリズムの手順

1. 初期値として最大辺の長さを 1 に設定します（中心要素のみの正方形）。
2. i を 0 から n/2 - 1 までループします。
3. 各 i に対して、対応する同心正方形の外周4辺（上・下・左・右）の要素を走査します。
4. 外周のすべての要素が同じ値であれば、その正方形の辺の長さ n - 2 * i を候補として記録します。
5. ループ終了後、記録された最大の辺の長さを返します。

C++による実装例

#include <iostream>
#define n 5
using namespace std;

int findMaxSideSquare(int matrix[][n]) {
    int squareLen = 1;
    for (int i = 0; i < n / 2; i++) {
        int sideVal = matrix[i][i];
        bool isSquare = true;
        for (int j = i; j < n - i; j++) {
            if (matrix[i][j] != sideVal)
                isSquare = false;
            if (matrix[n - i - 1][j] != sideVal)
                isSquare = false;
            if (matrix[j][i] != sideVal)
                isSquare = false;
            if (matrix[j][n - i - 1] != sideVal)
                isSquare = false;
        }
        if (isSquare)
            squareLen = n - 2 * i;
    }
    return squareLen;
}

int main() {
    int mat[n][n] = {
        {2, 4, 6, 6, 5},
        {1, 7, 7, 7, 3},
        {5, 7, 0, 7, 1},
        {3, 7, 7, 7, 1},
        {2, 0, 1, 3, 2}
    };
    cout<<"The maximum side length of square in a Matrix is "<<findMaxSideSquare(mat);
    return 0;
}

実行結果

The maximum side length of square in a Matrix is 3

計算量について

このアルゴリズムの時間計算量は O(n²) です。外側のループが n/2 回実行され、各反復で外周の走査に O(n) かかるためです。空間計算量は追加のデータ構造を使用しないため O(1) となり、非常に効率的な実装と言えます。