C++で行列内のエンドレスポイント(無限ポイント)の数を求める方法

問題概要

この問題では、2次元配列 mat[n][m] が与えられ、その行列に含まれる「エンドレスポイント(無限ポイント)」の総数を求めることが課題となります。

ある点がエンドレスポイントとみなされるのは、その点自身が1であり、かつ同じ列の下方向・同じ行の右方向にあるすべての要素も1である場合です。すなわち、

mat[i][j] がエンドレスポイントである条件:
mat[i][j]、mat[i+1][j] … mat[n-1][j](下方向)および
mat[i][j+1] … mat[i][m-1](右方向)がすべて1

具体例で問題を確認しましょう。

入力

mat[][] = { {0, 0},
            {1, 1} }

出力

2

解説

この例では、mat[1][0] と mat[1][1] の2点がエンドレスポイントです。mat[1][0] は自身が1で右隣の mat[1][1] も1であり、mat[1][1] は自身が1で右にも下にもこれ以上要素がないため、条件を満たします。

解法アプローチ

1. シンプルな解法(全探索)

最も単純な方法は、行列のすべての要素を走査し、各要素について右方向と下方向の要素を一つずつ実際に確認するものです。条件を満たす要素が見つかるたびにカウントを増やし、全要素のチェックが終わった時点でカウントを返します。ただしこの方法は時間計算量が O(n×m×(n+m)) となり、大きな行列では非効率です。

2. 効率的な解法(動的計画法)

動的計画法(DP)を活用すると、各点がエンドレスポイントかどうかを効率的に判定できます。ある点がエンドレスポイントであるためには、その行と列のそれ以降の要素がすべて1である必要があるため、次の2つのDPテーブルを用意します。

• rowDP[i][j]:要素 mat[i][j] 自身と、その右側の要素がすべて1であるかを表す
• colDP[i][j]:要素 mat[i][j] 自身と、その下側の要素がすべて1であるかを表す

これらのテーブルは右下から順に埋めていくことで、各マスを O(1) で計算できます。最後に、rowDP と colDP が両方とも1になっている点を数えれば、それがエンドレスポイントの総数となります。

C++での実装例

#include <iostream>
using namespace std;

const int N = 2;
const int M = 2;

// エンドレスポイントの数を数える関数
int countEndlessPoints(int mat[N][M]) {
    int rowDP[N][M], colDP[N][M];

    // 行方向のDP:自身と右側がすべて1かどうか
    for (int i = 0; i < N; i++) {
        rowDP[i][M - 1] = mat[i][M - 1];
        for (int j = M - 2; j >= 0; j--)
            rowDP[i][j] = (mat[i][j] == 1 && rowDP[i][j + 1] == 1) ? 1 : 0;
    }

    // 列方向のDP:自身と下側がすべて1かどうか
    for (int j = 0; j < M; j++) {
        colDP[N - 1][j] = mat[N - 1][j];
        for (int i = N - 2; i >= 0; i--)
            colDP[i][j] = (mat[i][j] == 1 && colDP[i + 1][j] == 1) ? 1 : 0;
    }

    // 両方の条件を満たす点をカウント
    int count = 0;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            if (rowDP[i][j] == 1 && colDP[i][j] == 1)
                count++;

    return count;
}

int main() {
    int mat[N][M] = {
        {0, 0},
        {1, 1}
    };

    cout << "エンドレスポイントの数: " << countEndlessPoints(mat);
    return 0;
}

出力

エンドレスポイントの数: 2

計算量の評価

• 時間計算量: O(n×m) — 各マスを定数時間で処理できる
• 空間計算量: O(n×m) — 行・列方向の2つのDPテーブルが必要

全探索では O(n×m×(n+m)) の計算量がかかるところを、動的計画法によって大幅に高速化できるのがこのアプローチの大きな利点です。