C++에서 체스판으로 변환

<시간/>

하나의 N x N 보드에 0과 1만 포함되어 있다고 가정합니다. 이제 각 이동에서 2개의 행 또는 2개의 열을 바꿀 수 있습니다. 보드를 "체스판"으로 변환하려면 최소 이동 수를 찾아야 합니다. 솔루션이 존재하지 않으면 -1을 반환합니다.

따라서 입력이 다음과 같으면 -

그러면 첫 번째 이동의 처음 두 열과 같이 출력이 2가 되고 보드는 다음과 같습니다. -

그런 다음 두 번째와 세 번째 행을 바꿉니다 -

이것은 체스판입니다

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

n :=b의 크기
초기화 i의 경우:=0, i
j 초기화의 경우:=0, j
b[0, 0] XOR b[0, j] XOR b[i, 0] XOR b[i, j]가 0이 아닌 경우 -
- 반환 -1

rowSum :=0, colSum :=0, rowSwap :=0, colSwap :=0

초기화 i의 경우:=0, i

rowSum :=rowSum + b[i, 0], colSum :=colSum + b[0, i]

rowSwap :=rowSwap + b[i, 0]이 i mod 2와 같을 때 true,

colSwap :=colSwap + b[0, i]가 i mod 2와 같을 때 true

rowSum이 n / 2와 같지 않고 rowSum이 (n + 1) / 2와 같지 않으면 -

반환 -1

colSum이 n / 2와 같지 않고 colSum이 (n + 1) / 2와 같지 않으면 -

반환 -1

n mod 2가 1과 같으면 -

colSwap mod 2가 0이 아닌 경우 -
- colSwap :=n - colSwap
rowSwap mod 2가 0이 아닌 경우 -
- rowSwap :=n - rowSwap

그렇지 않으면

colSwap :=colSwap 및 n의 최소값 - colSwap
rowSwap :=rowSwap의 최소값 및 n - rowSwap

반환(rowSwap + colSwap) / 2

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예

#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}};