Chuyển sang Chessboard trong C ++

Giả sử chúng ta có một bảng N x N chỉ chứa các số 0 và 1. Bây giờ trong mỗi lần di chuyển, chúng ta có thể hoán đổi 2 hàng hoặc 2 cột bất kỳ. Chúng ta phải tìm số nước đi tối thiểu để biến bàn cờ thành "bàn cờ". Nếu giải pháp không tồn tại, thì trả về -1.

Vì vậy, nếu đầu vào giống như -

Sau đó, đầu ra sẽ là 2, vì hai cột đầu tiên trong lần di chuyển đầu tiên, sau đó bảng sẽ giống như -

Sau đó, hoán đổi hàng thứ hai và thứ 3 -

Đây là bàn cờ

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của b
• để khởi tạo i:=0, khi i
• để khởi tạo j:=0, khi j
• nếu b [0, 0] XOR b [0, j] XOR b [i, 0] XOR b [i, j] khác 0, thì -
  • trả về -1

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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

Đầu vào

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

Đầu ra

2