C++でバイナリ行列をすべて1にするための最小操作回数を求めるアルゴリズム

問題概要

N行M列のバイナリ行列（各要素が0または1の行列）が与えられます。この行列に対して許可されている操作は、任意のインデックス (x, y) を選択し、左上を (0, 0)、右下を (x-1, y-1) とする長方形領域内のすべての要素を反転（トグル）することです。ここで「反転」とは、1を0に、0を1に変更することを意味します。

この問題の目的は、行列のすべての要素を1にするために必要な最小操作回数を求めることです。

具体例

入力行列：
{0, 0, 0, 1, 1}
{0, 0, 0, 1, 1}
{0, 0, 0, 1, 1}
{1, 1, 1, 1, 1}
{1, 1, 1, 1, 1}

答え：1

この場合、一度だけ操作を行えば十分です。(3, 3) を選択して左上の3×3の領域を反転させると、行列全体がすべて1になります。

アルゴリズムの考え方

この問題を解く鍵となるアイデアは、行列の右下端 (N-1, M-1) からスタートし、逆順に走査することです。

走査の過程で値が0のセルに出会ったら、そのセルを含む左上方向の長方形領域全体を反転します。右下から処理を進めることで、すでに確定した領域を壊さずに済むため、これが最適な戦略となります。

C++での実装例

#include <iostream>
#define ROWS 5
#define COLS 5
using namespace std;

int getMinOperations(bool arr[ROWS][COLS]) {
    int ans = 0;
    for (int i = ROWS - 1; i >= 0; i--){
        for (int j = COLS - 1; j >= 0; j--){
            if(arr[i][j] == 0){
                ans++;
                for (int k = 0; k <= i; k++){
                    for (int h = 0; h <= j; h++){
                        if (arr[k][h] == 1)
                            arr[k][h] = 0;
                        else
                            arr[k][h] = 1;
                    }
                }
            }
        }
    }
    return ans;
}

int main() {
    bool mat[ROWS][COLS] = {
        0, 0, 1, 1, 1,
        0, 0, 0, 1, 1,
        0, 0, 0, 1, 1,
        1, 1, 1, 1, 1,
        1, 1, 1, 1, 1
    };
    cout << "Minimum required operations = " << getMinOperations(mat) << endl;
    return 0;
}

実行結果

上記のプログラムをコンパイルして実行すると、次の出力が得られます。

Minimum required operations = 3

計算量について

この実装では、0のセルを見つけるたびに最大 O(N×M) の反転処理を行うため、最悪計算量は O((N×M)²) となります。より大規模な行列に対しては、差分配列や二次元累積和を活用することで、O(N×M) まで高速化できる点にも注目です。