মনে করুন, একটি N x N বোর্ড আছে যেটিতে শুধু ০ এবং ১ রয়েছে। প্রতিটি চলে আমরা যেকোনো ২টি সারি অথবা ২টি কলাম 스왪 করতে পারি। বোর্ডটিকে একটি "চেসবোর্ড" এ রূপান্তর করার জন্য ন্যূনতম চলে সংখ্যা বের করতে হবে। যদি সমাধান না থাকে, তবে -1 রিটার্ন করুন।
ইনপুট উদাহরণ:
আউটপুট হবে ২। প্রথমে দুটি কলাম সোয়াপ করলে, তারপর দ্বিতীয় ও তৃতীয় সারি সোয়াপ করলে চেসবোর্ড পাওয়া যায়।
সমাধানের ধাপসমূহ
- n := b.size()
- সকল i, j এর জন্য যদি b[0][0] ^ b[0][j] ^ b[i][0] ^ b[i][j] != 0 হয়, তবে -1 রিটার্ন করুন
- rowSum, colSum, rowSwap, colSwap := 0
- i := 0 থেকে n-1 পর্যন্ত
- rowSum += b[i][0], colSum += b[0][i]
- rowSwap += (b[i][0] == i%2), colSwap += (b[0][i] == i%2)
- যদি rowSum != n/2 এবং rowSum != (n+1)/2 হয়, -1 রিটার্ন করুন
- যদি colSum != n/2 এবং colSum != (n+1)/2 হয়, -1 রিটার্ন করুন
- যদি n%2 == 1 হয়
- যদি colSwap%2 হয়, colSwap := n - colSwap
- যদি rowSwap%2 হয়, rowSwap := n - rowSwap
- অন্যথায়
- colSwap := min(colSwap, n - colSwap)
- rowSwap := min(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}};
আউটপুট
2
