C++でブール行列を処理する方法：1の要素がある行と列をすべて1にするアルゴリズム

ブール行列とは

ブール行列（Boolean Matrix）とは、要素が「0」と「1」の2種類のみで構成される行列のことです。この問題では、m×n のサイズのブール行列 arr[m][n] が与えられます。求解条件は次のとおりです。

条件： もし m[i][j] = 1 であるなら、i 行目のすべての要素と j 列目のすべての要素を 1 にする。

具体例

入力と出力の例を見てみましょう。

入力: arr[2][2] =
1 0
0 0

出力: arr[2][2] =
1 1
1 0

説明： arr[0][0] = 1 であるため、0 行目のすべての要素（arr[0][0] = arr[0][1] = 1）と、0 列目のすべての要素（arr[0][0] = arr[1][0] = 1）が 1 に更新されます。

解法のアプローチ

この問題を効率的に解くために、2 つのフラグ変数（row_flag と col_flag）を用意し、1 行目と 1 列目を更新する必要があるかどうかを記録します。更新が必要な場合は flag = 1、不要であれば 0 を設定します。そして、このフラグの値に基づいて、行と列の要素の値を変更します。この手順を配列内のすべての要素に対して実行します。

このアルゴリズムのポイントは以下のとおりです。

• 1 行目と 1 列目を「マーカー」として活用することで、追加のメモリ使用量を O(1) に抑えられます。
• まず行列全体を走査し、mat[i][j] == 1 であれば mat[0][j] と mat[i][0] を 1 に設定します。
• 次に、1 行目・1 列目の情報を基に、内部の要素（1 行目と 1 列目を除く）を更新します。
• 最後に、フラグ変数の値に応じて 1 行目と 1 列目自体を更新します。

計算量は時間 O(m×n)、追加の空間計算量 O(1) となります。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
const int R = 3;
#define C 4
void matrixflip(int mat[R][C]) {
    int row_flag = 0;
    int col_flag = 0;
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (i == 0 && mat[i][j] == 1)
                row_flag = 1;
            if (j == 0 && mat[i][j] == 1)
                col_flag = 1;
            if (mat[i][j] == 1) {
                mat[0][j] = 1;
                mat[i][0] = 1;
            }
        }
    }
    for (int i = 1; i < R; i++) {
        for (int j = 1; j < C; j++) {
            if (mat[0][j] == 1 || mat[i][0] == 1) {
                mat[i][j] = 1;
            }
        }
    }
    if (row_flag) {
        for (int i = 0; i < C; i++) {
            mat[0][i] = 1;
        }
    }
    if (col_flag) {
        for (int i = 0; i < R; i++) {
            mat[i][0] = 1;
        }
    }
}
int main() {
    int mat[R][C] = { { 1, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 1, 0 } };
    cout << "Input Matrix :\n";
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cout << mat[i][j] << " ";
        }
        cout << endl;
    }
    matrixflip(mat);
    cout << "Matrix after bit flip :\n";
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cout << mat[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

実行結果

Input Matrix :
1 0 0 0
0 0 0 0
0 0 1 0
Matrix after bit flip :
1 1 1 1
1 0 1 0
1 1 1 1

まとめ

このアルゴリズムでは、行列の 1 行目と 1 列目をフラグとして再利用することで、追加のメモリをほとんど使わずに問題を解決できます。要素が 1 の位置を検出した際に、対応する行と列のマーカーを立て、その後まとめて更新を行うという流れがポイントです。計算量は O(m×n) と効率的で、大きな行列に対しても実用的な手法です。