C++で同じ値で構成される最大のk×k正方形部分行列を見つけるプログラム

問題の概要

2次元行列が与えられたとき、すべての要素が同じ値を持つ最大の k × k 部分行列（正方形）を見つけ、そのサイズ k の値を求めることを考えます。

例として、次の入力が与えられたとします。

この場合、値がすべて「5」である 3 × 3 の正方形行列が存在するため、出力は 3 となります。

解決アプローチ（動的計画法）

この問題は、動的計画法（DP）を用いることで効率的に解くことができます。各セルについて、そこを左上の頂点とする同一値の正方形がどこまで拡張できるかを計算していきます。具体的な手順は以下の通りです。

• n := 行列の行数

• m := 行列の列数

• サイズ n × m の2次元配列 dp を定義し、すべて 1 で初期化する

• ret := 1（結果を格納する変数）

• i を n - 1 から 0 まで減らしながら繰り返し：

  • j を m - 1 から 0 まで減らしながら繰り返し：

    • val := 無限大（INT_MAX）で初期化

    • i + 1 < n かつ v[i + 1][j] == v[i][j] の場合：
      val := min(dp[i + 1][j], val)

      それ以外の場合：val := 0

    • j + 1 < m かつ v[i][j + 1] == v[i][j] の場合：
      val := min(dp[i][j + 1], val)

      それ以外の場合：val := 0

    • i + 1 < n かつ j + 1 < m かつ v[i + 1][j + 1] == v[i][j] の場合：
      val := min(dp[i + 1][j + 1], val)

      それ以外の場合：val := 0

    • val が無限大のままであれば、次の反復へスキップ

    • dp[i][j] := dp[i][j] + val

    • ret := max(ret, dp[i][j])

• 最後に ret を返す

アルゴリズムのポイント

このDPでは、セル (i, j) の右・下・右下の3方向にあるセルが同じ値かどうかを確認し、それぞれの位置で形成可能な正方形のサイズの最小値に基づいて、現在のセルでの正方形サイズを更新します。隣接するセルが異なる値であれば、その方向には正方形を拡張できないため val が 0 になり、dp[i][j] は初期値の 1 のままになります。

C++実装例

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int solve(vector<vector<int>>& v) {
        int n = v.size();
        int m = v[0].size();
        vector<vector<int>> dp(n, vector<int>(m, 1));
        int ret = 1;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = m - 1; j >= 0; j--) {
                int val = INT_MAX;
                if (i + 1 < n && v[i + 1][j] == v[i][j]) {
                    val = min(dp[i + 1][j], val);
                }
                else {
                    val = 0;
                }
                if (j + 1 < m && v[i][j + 1] == v[i][j]) {
                    val = min(dp[i][j + 1], val);
                }
                else {
                    val = 0;
                }
                if (i + 1 < n && j + 1 < m && v[i + 1][j + 1] == v[i][j]) {
                    val = min(dp[i + 1][j + 1], val);
                }
                else {
                    val = 0;
                }
                if (val == INT_MAX)
                    continue;
                dp[i][j] += val;
                ret = max(ret, dp[i][j]);
            }
        }
        return ret;
    }
};
int solve(vector<vector<int>>& matrix) {
    return (new Solution())->solve(matrix);
}
int main(){
    vector<vector<int>> matrix = {
        {1, 1, 8, 3},
        {1, 5, 5, 5},
        {2, 5, 5, 5},
        {4, 5, 5, 5}
    };
    cout << solve(matrix);
}

入力

{ {1, 1, 8, 3}, {1, 5, 5, 5}, {2, 5, 5, 5}, {4, 5, 5, 5} };

出力

3

まとめ

本記事では、2次元行列内で同一の値で構成される最大の k × k 正方形部分行列のサイズを求める方法を解説しました。右・下・右下の3方向を参照する動的計画法により、時間計算量 O(n × m) で効率的に答えを導き出すことができます。