C++で全要素が等しい最大の正方形部分行列を求めるアルゴリズム

問題概要

この問題では、N×N の行列 mat[] が与えられ、すべての要素が等しい最大の正方形部分行列を見つけることが課題となります。

つまり、与えられた行列の中から、全要素が同じ値で構成される正方形部分行列のうち、最大のサイズを求める必要があります。

問題を理解するための具体例

入力: mat[][] = {{1, 2, 1}, {1, 2, 2}, {2, 2, 2}}
出力: 2

説明:

a11, a12, a21, a22 の位置にある要素は 2×2 の正方形を形成し、すべて同じ値(2)で構成されています。

解法アプローチ

単純な解法(総当たり): 行列のすべての要素を走査し、考えられるすべての部分行列について「全要素が同じかどうか」を確認する方法です。この場合、走査自体に O(n³) の時間計算量がかかり、さらに各部分行列の検証にも O(n²) を要するため、大規模な行列には不向きです。

効率的な解法(動的計画法): 動的計画法(DP)を用いることで、より効率的にこの問題を解けます。各マス (i, j) に対して「その位置を右下とする、全要素が等しい正方形部分行列の最大サイズ」を DP 表に格納していきます。その際、左・上・左上の隣接セルの値を参照しながら、条件を満たす最大の正方形を求めます。DP 表の各セルの値は、次のように定式化できます。

セル (i, j) の要素が、上・左・左上のいずれとも同じ値である場合、DP の値を次のように更新します。

DP[i][j] = min(DP[i-1][j], DP[i][j-1], DP[i-1][j-1]) + 1

隣接する要素が異なる場合は、そのセル自身から新たな正方形が始まるとみなし、

DP[i][j] = 1

とします。

アルゴリズムのポイント

• DP[i][j] は、セル (i, j) を右下の角とする「全要素が等しい正方形部分行列」の最大辺の長さを表します。
• 1行目と1列目のセルは、それ自身しか正方形を構成できないため、DP の値は 1 で初期化されます。
• DP 表をすべて埋め終えたあとの最大値が答えとなります。
• 時間計算量・空間計算量はともに O(n²) で、総当たり法よりも大幅に効率的です。

C++による実装例

以下は、この解法の動作を示す C++ プログラムです。

#include<bits/stdc++.h>
#define n 4
#define m 4
using namespace std;
int findmaxSqMatSize(int mat[][m]){
   int DP[n][m];
   memset(DP, 0, sizeof(DP));
   int maxSqMatSize = 0;
   for (int i = 0 ; i < n ; i++){
      for (int j = 0 ; j < m ; j++){
         if (i == 0 || j == 0)
            DP[i][j] = 1;
         else{
            if (mat[i][j] == mat[i-1][j] && mat[i][j] == mat[i][j-1] && mat[i][j] == mat[i-1][j-1] )
               DP[i][j] = min(min(DP[i-1][j], DP[i][j-1]), DP[i-1][j-1] ) + 1;
            else DP[i][j] = 1;
         }
         maxSqMatSize = max(maxSqMatSize, DP[i][j]);
      }
   }
   return maxSqMatSize;
}
int main(){
   int mat[n][m] = { {2, 1, 4, 3},
   {5, 1, 1, 7},
   {1, 1, 1, 4},
   {9, 4, 6, 0}};
   cout<<"The maximum square sub-matrix with all equal elements is "<<findmaxSqMatSize(mat);
   return 0;
}

実行結果

The maximum square sub-matrix with all equal elements is 2

(日本語訳:「全要素が等しい最大の正方形部分行列のサイズは 2 です」。この入力では、値 1 で構成される 2×2 の部分行列が最大となります。)