home

หน้าแรก
 Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

แปลงเป็นกระดานหมากรุกใน C ++

สมมติว่าเรามีบอร์ด N x N อันที่มีเพียง 0s และ 1s เท่านั้น ในการย้ายแต่ละครั้ง เราสามารถสลับ 2 แถวหรือ 2 คอลัมน์ใดก็ได้ เราต้องหาจำนวนการเคลื่อนไหวขั้นต่ำเพื่อเปลี่ยนกระดานให้เป็น "กระดานหมากรุก" หากไม่มีวิธีแก้ปัญหา ให้คืนค่า -1

ดังนั้นหากอินพุตเป็นแบบ −














จากนั้นผลลัพธ์จะเป็น 2 เนื่องจากสองคอลัมน์แรกในการย้ายครั้งแรก กระดานจะเป็นแบบนี้ -














จากนั้นสลับแถวที่สองและแถวที่ 3 -














นี่คือกระดานหมากรุก

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

  • n :=ขนาดของ b
  • สำหรับการเริ่มต้น i :=0 เมื่อฉัน
  • สำหรับการเริ่มต้น 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 เมื่อฉัน
  • 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 ใช้ namespace std;class Solution {public:int movesToChessboard(vector>&b) { int n =b.size(); for(int i =0; i > 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