C++ এ চেসবোর্ডে রূপান্তর করুন

ধরুন আমাদের একটি N x N বোর্ডে শুধুমাত্র 0s এবং 1s আছে। এখন প্রতিটি পদক্ষেপে, আমরা যেকোনো 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] অ-শূন্য হয়, তাহলে −
- রিটার্ন -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 এর মত হয়,

colSwap :=সত্য যখন colSwap + b[0, i] i mod 2 এর মত হয়

যদি rowSum n / 2 এর সমান না হয় এবং rowSum (n + 1) / 2 এর সমান না হয়, তাহলে −

রিটার্ন -1

যদি colSum n / 2 এর সমান না হয় এবং colSum (n + 1) / 2 এর সমান না হয়, তাহলে −

রিটার্ন -1

যদি n mod 2 1 এর মত হয়, তাহলে −

যদি colSwap mod 2 অ-শূন্য হয়, তাহলে −
- colSwap :=n - colSwap
যদি rowSwap mod 2 অ-শূন্য হয়, তাহলে −
- rowSwap :=n - rowSwap

অন্যথায়

colSwap :=ন্যূনতম colSwap এবং n - colSwap
সারি অদলবদল :=ন্যূনতম সারি অদলবদল এবং n - সারি অদলবদল

রিটার্ন (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}};