C++でバイナリ行列をゼロ行列に変換する演算の数をカウントするプログラム

バイナリ行列があるとします。ここで、1つのセルを取得し、そのセルとそのすべての隣接セル（上、下、左、右）を反転する操作について考えてみます。行列に0のみが含まれるように、必要な操作の最小数を見つける必要があります。解決策がない場合は、-1を返します。

したがって、入力が次のような場合

その場合、出力は3になります。

これを解決するには、次の手順に従います-

• サイズの配列ディレクトリを定義します：4 x 2：={{1、0}、{0、1}、{-1、0}、{0、-1}}
• const int inf =10 ^ 6
• 関数getPos（）を定義します。これには、i、j、
が必要です。
• return i * c + j
• 1つの関数getCoord（）を定義します。これにはxが必要です
  • 1ペアのretを定義する
  • ret [0]：=x / c
  • ret [1]：=x mod c
  • return ret
• メインの方法から次の手順を実行します。
• マスク：=0
• r：=行列の行数
• c：=行列の列数
• 最後：=r * c
• iを初期化する場合：=0、i
• jを初期化する場合：=0、j
• mask：=mask XOR（matrix [i、j] * 2 ^ getPos（i、j））

理解を深めるために、次の実装を見てみましょう-

例

#include
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 getCoord(int x){
   pair ret;
   ret.first = x / c;
   ret.second = x % c;
   return ret;
}

int solve(vector>& 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 dist(1 << 9, -1);
   queue q;
   q.push(mask);
   dist[mask] = 0;
   while(!q.empty()){
      mask = q.front();
      q.pop();
     
      for(int i = 0; i < last; i++){
         pair 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> v = {{0, 0},{1, 0}};
   cout << solve(v);
}

入力

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

出力

3