C++で2値行列から「1」だけで形成される最大の「+」のサイズを求める方法

問題概要

この記事では、N×Nの2値行列（バイナリ行列）bin[][] が与えられたとき、すべて「1」で構成される最大の「+」（プラス形）のサイズを求めるアルゴリズムを解説します。

まず、具体例を使って問題を確認しましょう。

入力

0 1 1
1 1 1
0 1 0

出力

5

この例では、中央の要素を中心として、上下左右の各方向に1個ずつ「1」が連続しています。したがって、「+」のサイズは「中心の1個＋各方向1個×4＝5」となります。

解法アプローチ

この問題に対する基本的な考え方は以下のとおりです。

• 行列上の各マスが「1」である場合、そのマスを中心とした上下左右の4方向それぞれに、何個の「1」が連続しているかを調べる必要があります。
• そのために、方向ごとに1つずつ、合計4つの補助行列を作成します。各補助行列には、対応する方向における連続する「1」の個数を格納します。
• すべてのインデックスについて、4方向それぞれの連続する「1」の個数の最小値を計算し、その中で最大の値（maxConOne）を求めます。

最大の「+」のサイズは、次の式で求められます。

サイズ = 4 × (maxConOne − 1) + 1

これは、「+」の中心から各方向へ (maxConOne − 1) 個ずつ腕が伸びるため、腕の部分が 4 × (maxConOne − 1) 個、中心が1個という構造になるためです。

C++による実装例

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

#include <iostream>
using namespace std;
#define N 7
int findLargestPlusSize(int mat[N][N]) {
    int conOneLeft[N][N], conOneRight[N][N], conOneTop[N][N], conOneBottom[N][N];
    for (int i = 0; i < N; i++) {
        conOneTop[0][i] = mat[0][i];
        conOneBottom[N - 1][i] = mat[N - 1][i];
        conOneLeft[i][0] = mat[i][0];
        conOneRight[i][N - 1] = mat[i][N - 1];
    }
    for (int i = 0; i < N; i++) {
        for (int j = 1; j < N; j++) {
            if (mat[i][j] == 1)
                conOneLeft[i][j] = conOneLeft[i][j - 1] + 1;
            else
                conOneLeft[i][j] = 0;
            if (mat[j][i] == 1)
                conOneTop[j][i] = conOneTop[j - 1][i] + 1;
            else
                conOneTop[j][i] = 0;
            j = N - 1 - j;
            if (mat[j][i] == 1)
                conOneBottom[j][i] = conOneBottom[j + 1][i] + 1;
            else
                conOneBottom[j][i] = 0;
            if (mat[i][j] == 1)
                conOneRight[i][j] = conOneRight[i][j + 1] + 1;
            else
                conOneRight[i][j] = 0;
            j = N - 1 - j;
        }
    }
    int maxConOne = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++){
            int ConOnes = min(min(conOneTop[i][j],
            conOneBottom[i][j]), min(conOneLeft[i][j], conOneRight[i][j]));
            if(ConOnes > maxConOne)
                maxConOne = ConOnes;
        }
    }
    if (maxConOne)
        return (4 * (maxConOne - 1) + 1);
    return 0;
}
int main() {
    int mat[N][N] = {
        { 1, 0, 1, 1, 1, 1, 0 },
        { 1, 0, 1, 0, 1, 1, 1 },
        { 1, 1, 1, 0, 1, 1, 0 },
        { 0, 0, 0, 0, 1, 0, 0 },
        { 1, 0, 1, 1, 1, 1, 1 },
        { 1, 1, 1, 0, 1, 1, 1 },
        { 1, 0, 0, 0, 1, 0, 0 },
    };
    cout<<"The size of the largest plus formed by ones is "<<findLargestPlusSize(mat);
    return 0;
}

出力

The size of the largest plus formed by ones is 9

コードのポイント

• conOneLeft / conOneRight / conOneTop / conOneBottom： それぞれ左・右・上・下方向への連続する「1」の個数を格納する補助行列です。
• ループ内では j = N - 1 - j; を使って行頭と行末から同時に走査することで、1回のループで左右（および上下）両方向の累積カウントを効率よく計算しています。
• 最後に全マスを走査し、4方向の最小値の中で最大となる maxConOne を求めて、「+」のサイズを計算します。

計算量

• 時間計算量： O(N²) — 行列の全マスを定数回走査するだけなので高速です。
• 空間計算量： O(N²) — 4つの補助行列を保持するために追加メモリが必要です。

まとめ

2値行列から最大の「+」を見つける問題は、4方向からの連続する「1」の個数を事前に計算しておくことで、効率的に解くことができます。累積結果を再利用する動的計画法の考え方を応用した典型的なパターンであり、類似のグリッド問題にも応用できる有用なテクニックです。