【C++】バイナリ行列をすべて0に変換するための最小操作回数を求めるプログラム

問題概要

0と1のみから構成されるバイナリ行列が与えられます。使用できる操作は「任意の1つのセルを選び、そのセル自身と上下左右の隣接するセル(存在する場合のみ)をすべて反転(0→1、1→0)する」というものです。この操作を繰り返して行列の全要素を0にするために必要な最小操作回数を求めてください。どのように操作してもすべて0にできない場合は -1 を返します。

入力例

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

これは次のような2×2の行列です。

出力

3

この場合、必要な操作回数は3回となります。

解法のアプローチ

この問題は、行列の状態をビットマスク(整数)として表現し、幅優先探索(BFS)で最短操作回数を求めることで解けます。行列の各状態は最大 r×c ビットの整数で表せるため、到達しうる状態数は高々 2^(r×c) 個です。本実装では最大9ビット(3×3行列まで)を想定しています。

アルゴリズムの手順

• 方向配列 dir(4×2)を {{1,0}, {0,1}, {-1,0}, {0,-1}} として定義します(下・右・上・左)。
• getPos(i, j): セル(i, j)の2次元座標を1次元のビット位置「i * c + j」に変換して返します。
• getCoord(x): 1次元のビット位置 x を(row, col)のペアに復元します。
• メインの solve() 関数では以下を実行します。
  • mask := 0 とし、r := 行数、c := 列数、last := r * c を設定します。
  • すべてのセルを走査し、「mask ^= (matrix[i][j] << getPos(i, j))」により初期状態をビットマスクへエンコードします。
  • サイズ512(= 2^9)の dist 配列を -1 で初期化します。-1 は「未訪問」を意味します。
  • キュー q に初期マスクを push し、dist[mask] := 0 とします。
  • キューが空になるまで以下を繰り返します(BFS)。
    • キューの先頭から mask を取り出します。
    • 各セル i(0 ≤ i < last)について、そのセルと隣接セルを反転した新しいマスク nmask を計算します。範囲外の隣接セルはスキップします。
    • nmask が未訪問(dist[nmask] == -1)、または既知の距離より短い場合は、dist[nmask] := dist[mask] + 1 と更新し、nmask をキューに追加します。
• 最後に dist[0](全セルが0の状態)を返します。到達不可能な場合は -1 のまま返ります。

C++実装例

#include <bits/stdc++.h>
using namespace std;

int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int c;
int r;
int last;
const int inf = 1e6;

int getPos(int i, int j){
    return i * c + j;
}

pair<int, int> getCoord(int x){
    pair<int, int> ret;
    ret.first = x / c;
    ret.second = x % c;
    return ret;
}

int solve(vector<vector<int>>& matrix) {
    int mask = 0;
    r = matrix.size();
    c = r ? matrix[0].size() : 0;
    last = r * c;
    for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++){
            mask ^= (matrix[i][j] << getPos(i, j));
        }
    }
    vector<int> dist(1 << 9, -1);
    queue<int> q;
    q.push(mask);
    dist[mask] = 0;
    while(!q.empty()){
        mask = q.front();
        q.pop();

        for(int i = 0; i < last; i++){
            pair<int, int> coord = getCoord(i);
            int x = coord.first;
            int y = coord.second;

            int nmask = mask;
            nmask ^= (1 << i);
            for(int k = 0; k < 4; k++){
                int nx = x + dir[k][0];
                int ny = y + dir[k][1];
                if(nx < 0 || nx >= r || ny < 0 || ny >= c)
                    continue;
                int pos = getPos(nx, ny);
                nmask ^= (1 << pos);
            }

            if(dist[nmask] == -1 || dist[nmask] > dist[mask] + 1){
                dist[nmask] = dist[mask] + 1;
                q.push(nmask);
            }
        }
    }
    return dist[0];
}

int main(){
    vector<vector<int>> v = {{0, 0},{1, 0}};
    cout << solve(v);
}

入力

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

出力

3

計算量とポイント

状態数は最大 2^9 = 512、各状態からの遷移は最大 last(≤9)通りであるため、計算量は O(2^(r×c) × r × c) 程度に収まり、小さな行列であれば十分高速に動作します。各操作は可逆であるため、BFSを採用することですべて0に至る最短手順が保証されます。また、dist[0] が -1 のままの場合は、その行列がどのような操作でもすべて0にできないことを示します。