C++でバイナリ行列をゼロ行列に変換するための最小反転回数を求める方法

m × n のバイナリ行列（0 と 1 のみで構成された行列）mat が与えられます。1 ステップごとに、任意のセルを 1 つ選び、そのセルのビットと、存在する場合は上下左右 4 つの隣接セルのビットをすべて同時に反転することができます。mat をゼロ行列（全要素が 0 の行列）へ変換するために必要な最小ステップ数を求めてください。解が存在しない場合は -1 を返します。

たとえば、入力が [[0,0], [0,1]] の場合、変換の過程は次のようになります。

この場合、3 ステップが必要となるため、出力は 3 になります。

解き方のアプローチ：BFS（幅優先探索）とビットマスク

この問題は幅優先探索（BFS）を用いることで効率的に解くことができます。鍵となるのは、行列全体の状態を 1 つの整数（ビットマスク）として表現することです。こうすることで、行列の各状態をグラフのノード、1 回の反転操作をエッジとみなした「最短経路問題」に帰着でき、BFS によって必ず最小ステップ数が得られます。

具体的な手順は以下の通りです。

• n := 行数、m := 列数、x := 0 と初期化します。
• 各行 i・各列 j について、mat[i][j] の値を ((i * m) + j) ビット分だけ左シフトした値を x に加算し、行列全体を 1 つの整数 x にエンコードします。
• サイズ 2^(n * m) の配列 dp を定義し、すべて -1 で埋めます（未訪問の目印として使います）。
• dp[x] := 0 とし、キュー q を用意して x を挿入します。
• q が空でない限り、以下を繰り返します。
• q の先頭要素を current として取り出します。
• current が 0（＝ゼロ行列）であれば、dp[current] を返します。
• すべてのセル (i, j) について、そのセルと隣接セルを反転した結果の状態 temp を計算します。範囲外にはみ出す隣接セルはスキップします。
• dp[temp] が -1（未訪問）であれば、dp[temp] := dp[current] + 1 と更新し、temp を q に挿入します。
• 探索を終えてもゼロ行列に到達できない場合は、-1 を返します。

BFS は状態を「近い順（ステップ数の少ない順）」に探索するため、初めてゼロ行列に到達した時点のステップ数が自動的に最小値となります。また、同じ状態を二度以上処理しないよう dp 配列で訪問管理を行うことで、無駄な探索を防いでいます。

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

実装例

#include <bits/stdc++.h>
using namespace std;
int dir[4][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
class Solution {
public:
   int minFlips(vector<vector<int>>& mat) {
      int n = mat.size();
      int m = mat[0].size();
      int x = 0;
      for(int i = 0; i < n; i++){
         for(int j = 0; j < m; j++){
            x += (mat[i][j] << ((i * m) + j));
         }
      }
      vector < int > dp(1 << (n*m), -1);
      dp[x] = 0;
      queue <int> q;
      q.push(x);
      while(!q.empty()){
         int current = q.front();
         q.pop();
         if(current == 0)return dp[current];
         for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
               int temp = current;
               temp ^= (1 << ((i *m) + j));
               for(int k = 0; k < 4; k++){
                  int ni = i + dir[k][0];
                  int nj = j + dir[k][1];
                  if(ni < 0 || nj < 0 || ni >= n || nj >= m)continue;
                  temp ^= (1 << ((ni *m) + nj));
               }
               if(dp[temp] == -1){
                  dp[temp] = dp[current] + 1;
                  q.push(temp);
               }
            }
         }
      }
      return -1;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{0,0},{0,1}};
   cout << (ob.minFlips(v));
}

入力

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

出力

3

計算量について

行列の状態数は最大 2^(n × m) 通りあり、各状態から遷移を生成するのに O(n × m) の計算が必要です。したがって、時間計算量は O(2^(n × m) × n × m)、空間計算量は dp 配列とキューのため O(2^(n × m)) となります。このため、この手法は n × m が小さい場合（LeetCode の制約では n × m ≤ 18 など）に現実的な解法となります。