C++で盤面をチェス盤に変換する：最小手数を求めるアルゴリズム

問題概要

0と1のみで構成される N × N の盤面が与えられたとします。各操作では、任意の2つの行、または任意の2つの列を入れ替えることが可能です。このとき、盤面を「チェス盤」のパターンに変換するために必要な最小の操作回数を求めてください。変換が不可能な場合は -1 を返します。

入力例

たとえば、次のような盤面が与えられたとします。

この場合の出力は 2 になります。

変換の手順

第1操作： まず2列目と3列目を入れ替えます。すると盤面は次のようになります。

第2操作： 続いて2行目と3行目を入れ替えます。

これで盤面は完全なチェス盤パターンになりました。

解法のアプローチ

この問題は、以下の手順で解くことができます。

• n を盤面 b のサイズとする
• i を 0 から n 未満まで増加させながら繰り返す：
  • j を 0 から n 未満まで増加させながら繰り返す：
    • b[0][0] XOR b[0][j] XOR b[i][0] XOR b[i][j] の結果が非ゼロの場合は -1 を返す
• rowSum := 0、colSum := 0、rowSwap := 0、colSwap := 0 で初期化する
• i を 0 から n 未満まで増加させながら繰り返す：
  • rowSum := rowSum + b[i][0]、colSum := colSum + b[0][i]
  • rowSwap += (b[i][0] == i % 2)
  • colSwap += (b[0][i] == i % 2)
• rowSum が n/2 にも (n+1)/2 にも等しくない場合は -1 を返す
• colSum が n/2 にも (n+1)/2 にも等しくない場合は -1 を返す
• n が奇数の場合：
  • colSwap が奇数なら、colSwap := n - colSwap
  • rowSwap が奇数なら、rowSwap := n - rowSwap
• それ以外の場合：
  • colSwap := min(colSwap, n - colSwap)
  • rowSwap := min(rowSwap, n - rowSwap)
• (rowSwap + colSwap) / 2 を返す

アルゴリズムのポイント

このアルゴリズムの鍵となるのは、XOR演算による妥当性チェックです。チェス盤パターンでは隣接するセルが必ず異なる値を持つため、任意の位置 (i, j) において b[0][0] ^ b[0][j] ^ b[i][0] ^ b[i][j] が常に 0 にならなければなりません。この条件が崩れている盤面は、行や列をどれだけ入れ替えてもチェス盤にはできません。

また、チェス盤では各行・各列に含まれる 1 の個数が、偶数サイズならちょうど n/2、奇数サイズなら (n+1)/2 または n/2 である必要があります。そのため、変換可能性の判定としてこの条件も事前に確認しています。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int movesToChessboard(vector<vector<int>>& b) {
      int n = b.size();
      for(int i = 0; i < n; i++){
         for(int j = 0; j < n; j++){
            if(b[0][0] ^ b[0][j] ^ b[i][0] ^ b[i][j]) return -1;
         }
      }
      int rowSum = 0;
      int colSum = 0;
      int rowSwap = 0;
      int colSwap = 0;
      for(int i = 0; i < n; i++){
         rowSum += b[i][0];
         colSum += b[0][i];
         rowSwap += b[i][0] == i % 2;
         colSwap += b[0][i] == i % 2;
      }
      if(rowSum != n/2 && rowSum != (n + 1)/2)return -1;
      if(colSum != n/2 && colSum != (n + 1)/2)return -1;
      if(n % 2 == 1){
         if(colSwap % 2) colSwap = n - colSwap;
         if(rowSwap % 2) rowSwap = n - rowSwap;
      }else{
         colSwap = min(colSwap, n - colSwap);
         rowSwap = min(rowSwap, n - rowSwap);
      }
      return (rowSwap + colSwap)/2;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{0,1,1,0},{0,1,1,0},{1,0,0,1},{1,0,0,1}};
   cout << (ob.movesToChessboard(v));
}

入力

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

出力

2