C++で指定された行列内のすべてが1の部分行列の数を数えるプログラム

問題の概要

2次元のバイナリ行列（各要素が0または1の行列）が与えられたとき、すべての要素が1で構成されている部分行列の総数を求めることを考えます。

たとえば、次のような入力が与えられた場合を考えてみましょう。

この場合の出力は10になります。これは、1×1の行列が5個、2×1の行列が2個、1×2の行列が2個、さらに2×2の行列が1個存在するためです。

解決アプローチ

この問題は、各行をヒストグラムとして捉え、単調スタック（monotonic stack）を利用することで効率的に解くことができます。具体的には、各行までの「連続する1の高さ」を記録した配列を作成し、その配列に対して各位置を右端とする部分行列の数を累積的に計算していきます。

この問題を解くために、以下の手順に従います。

• 関数getAns()を定義します。この関数は配列aを受け取ります。
• ret := 0 と初期化します。
• n := 配列aのサイズとします。
• サイズnの配列vを定義します。
• スタックstを1つ用意します。
• i := 0 から 配列aのサイズ未満の間、iを1ずつ増やしながら以下を実行します。
  • スタックstが空でなく、かつ a[stのトップ要素] >= a[i] を満たす間、stから要素を取り出します（pop）。
  • stが空でない場合は、次のように処理します。
    • prev := stのトップ要素
    • v[i] := v[i] + v[prev]
    • v[i] := v[i] + a[i] × (i − prev)
  • stが空の場合は、次のように処理します。
    • v[i] := v[i] + a[i] × (i + 1)
  • i を st に挿入します（push）。
• 配列vの各要素iについて、ret := ret + i として合計します。
• ret を返します。

続いて、メインメソッドでは以下の手順を実行します。

• ret := 0 と初期化します。
• n := 行列vの行数とします。
• m := （nが0でなければ v[0] のサイズ、そうでなければ 0）とします。
• サイズmの配列tempを定義します。
• i := 0 から n 未満の間、以下を繰り返します。
  • j := 0 から m 未満の間、以下を繰り返します。
    • temp[j] := （v[i][j] が0でなければ temp[j] + 1、そうでなければ 0）
  • ret := ret + getAns(temp)
• ret を返します。

実装例

それでは、理解を深めるために実際のC++コードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int getAns(vector<int>& a) {
        int ret = 0;
        int n = a.size();
        vector<int> v(n);
        stack<int> st;
        for (int i = 0; i < a.size(); i++) {
            while (!st.empty() && a[st.top()] >= a[i])
                st.pop();
            if(!st.empty()) {
                int prev = st.top();
                v[i] += v[prev];
                v[i] += a[i] * (i - prev);
            }
            else{
                v[i] += a[i] * (i + 1);
            }
            st.push(i);
        }
        for (int i : v) {
            ret += i;
        }
        return ret;
    }
    int solve(vector<vector<int>>& v) {
        int ret = 0;
        int n = v.size();
        int m = n ? v[0].size() : 0;
        vector<int> temp(m);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                temp[j] = v[i][j] ? temp[j] + 1 : 0;
            }
            ret += getAns(temp);
        }
        return ret;
    }
};
int solve(vector<vector<int>>& matrix) {
    return (new Solution())->solve(matrix);
}
main(){
    vector<vector<int>> matrix = {
        {1, 1, 0},
        {1, 1, 0},
        {0, 0, 1}
    };
    cout << solve(matrix);
}

入力

{{1, 1, 0},{1, 1, 0},{0, 0, 1}};

出力

10

このアルゴリズムの計算量は O(N×M) であり、行列のすべてのセルを一度ずつ処理するため、大きな行列に対しても効率的に動作します。