C++で行列内の同じ長方形領域の合計を持つセルを出力する方法

問題の概要

この記事では、整数値を要素とする m×n サイズの行列 mat が与えられたとき、同じ長方形領域の合計を持つセルを行列から出力するプログラムをC++で作成します。

問題の説明： 行列の中からあるセルを見つけ出し、そのセルを境界として得られる2つの部分行列（左上の領域と右下の領域）の合計が、残りのすべての要素の合計と等しくなるようにします。

言い換えると、セル (a, b) において、mat[0][0] から mat[a][b] までの部分行列と、mat[a][b] から mat[m-1][n-1] までの部分行列の合計（重複するセルは1回だけカウント）が、それ以外の要素の合計と一致していれば、そのセルが条件を満たします。

入力例と出力例

入力：

mat[][] = { {5, 0, 2, 7},
            {3, 0, 1, 0},
            {1, 4, 1, 3},
            {10, 0, 2, 1} }

出力：(2, 1)

説明：

セル (2, 1) に着目してみましょう。

部分行列1（左上からセル (2, 1) まで）は次のようになります。

{ {5, 0},
  {3, 0},
  {1, 4} }

部分行列2（セル (2, 1) から右下まで）は次のようになります。

{ {4, 1, 3},
  {0, 2, 1} }

両方の部分行列の合計（重複するセルは1回だけ数える）は以下の通りです。

合計 ＝ 5 + 0 + 3 + 0 + 1 + 4 + 1 + 3 + 0 + 2 + 1 ＝ 20

一方、残りの要素の合計は以下の通りです。

残りの合計 ＝ 2 + 7 + 1 + 0 + 10 ＝ 20

両者の値が一致しているため、セル (2, 1) が求める答えとなります。

解決のためのアプローチ

この問題を効率的に解くには、2つの補助行列 aux1[m][n] と aux2[m][n] を用意します。

• aux1[i][j]：左上 (0, 0) からセル (i, j) までの全要素の累積和を格納します。
• aux2[i][j]：セル (i, j) から右下 (m-1, n-1) までの全要素の累積和を格納します。

その後、両方の累積和を加算し、2回重複してカウントされる mat(i, j) の分を1回引きます。この値が行列全体の合計の半分と等しければ、そのセルは条件を満たしていることになります。該当するセルを見つけたら、その座標を出力します。

この手法により、各セルについて毎回合計を再計算する必要がなくなり、時間計算量は O(m×n) で抑えられます。

ソリューションの実装例

以下は、上記のアプローチを実装したC++プログラムです。

#include <iostream>
using namespace std;
#define R 4
#define C 4

void findCellWithSameRectSum(int mat[R][C]) {

    int m = R, n = C;
    int aux1[m][n], aux2[m][n];
    int matSum = 0;

    for (int i = 0; i < m; i++) {
       for (int j = 0; j < n; j++) {

          aux2[i][j] = aux1[i][j] = mat[i][j];
          matSum += mat[i][j];

       }
    }

    for (int i = 1; i < m; i++) {

        aux1[i][0] += aux1[i-1][0];
        aux2[m-i-1][n-1] += aux2[m-i][n-1];
    }

    for (int j = 1; j < n; j++) {

        aux1[0][j] += aux1[0][j-1];
        aux2[m-1][n-j-1] += aux2[m-1][n-j];
    }

    for (int i = 1; i < m; i++)
       for (int j = 1; j < n; j++) {

          aux1[i][j] += aux1[i-1][j] + aux1[i][j-1] - aux1[i-1][j-1];
          aux2[m-i-1][n-j-1] += aux2[m-i][n-j-1] + aux2[m-i-1][n-j] - aux2[m-i][n-j];
      }

    for (int i = 0; i < m; i++)
       for (int j = 0; j < n; j++)
          if (matSum == 2 * (aux1[i][j] + aux2[i][j] - mat[i][j]))
             cout << "(" << i << ", " << j << ")\t";
}

int main() {
    int mat[R][C] = {{5, 0, 2, 7},
                     {3, 0, 1, 0},
                     {1, 4, 1, 3},
                     {10, 0, 2, 1}};
    cout<<"The cells with same rectangular sums in a matrix is \n";
    findCellWithSameRectSum(mat);

    return 0;
}

出力結果

The cells with same rectangular sums in a matrix is
(1, 1)          (2, 1)

このように、条件を満たすセル (1, 1) と (2, 1) が出力されました。