C++ में शतरंज बोर्ड में परिवर्तन (Transform to Chessboard)

मान लीजिए हमारे पास एक N x N बोर्ड है जिसमें केवल 0 और 1 हैं। अब प्रत्येक चाल में, हम किन्हीं 2 पंक्तियों (rows), या किन्हीं 2 स्तंभों (columns) को स्वैप कर सकते हैं। हमें बोर्ड को "शतरंज बोर्ड" (chessboard) में बदलने के लिए न्यूनतम चालों की संख्या ज्ञात करनी है। यदि समाधान मौजूद नहीं है, तो -1 वापस करें।

तो यदि इनपुट इस प्रकार है -

तो आउटपुट 2 होगा, क्योंकि पहले दो स्तंभों को पहले चाल में स्वैप करें, फिर बोर्ड इस प्रकार होगा -

फिर दूसरी और तीसरी पंक्तियों को स्वैप करें -

यह शतरंज बोर्ड है।

इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे -

• n := b का आकार
• i := 0 से प्रारंभ करें, जब i < n, i बढ़ाते हुए, करें -
  • j := 0 से प्रारंभ करें, जब j < n, 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 < n, i बढ़ाते हुए, करें -
  • rowSum := rowSum + b[i, 0], colSum := colSum + b[0, i]
  • rowSwap := true जब rowSwap + b[i, 0], i mod 2 के समान है,
  • colSwap := true जब 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 का न्यूनतम
  • 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}};

आउटपुट

2