ภาพรวมปัญหา
สมมติว่ามีกระดาน N x N ที่มีแค่ 0 และ 1 ในแต่ละการเคลื่อนที่ เราสามารถสลับแถว 2 แถว หรือคอลัมน์ 2 คอลัมน์ ได้ ต้องการหาจำนวนการเคลื่อนที่น้อยที่สุดเพื่อทำให้กระดานกลายเป็น "กระดานหมากรุก" (สลับ 0 และ 1 ทีละเซลล์) หากไม่มีคำตอบ คืนค่า -1
ตัวอย่าง
Input: {{0,1,1,0},{0,1,1,0},{1,0,0,1},{1,0,0,1}} → Output: 2
สลับคอลัมน์ 1-2 แล้วสลับแถว 2-3
แนวทางแก้ปัญหา
- ตรวจสอบเงื่อนไขจำเป็น: b[0][0] XOR b[0][j] XOR b[i][0] XOR b[i][j] == 0 สำหรับทุก i,j
- นับ rowSum, colSum (จำนวน 1 ในแถวแรกและคอลัมน์แรก) ต้องเป็น n/2 หรือ (n+1)/2
- นับ rowSwap, colSwap (จำนวนตำแหน่งที่ไม่ตรงกับรูปแบบหมากรุก)
- ถ้า n คี่: rowSwap และ colSwap ต้องเป็นเลขคู่ (ปรับให้เป็น n - swap ถ้าจำเป็น)
- ถ้า n คู่: ใช้ min(swap, n - swap)
- คำตอบ = (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, colSum = 0, rowSwap = 0, 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;
}
};
int 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));
}
Input
{{0,1,1,0},{0,1,1,0},{1,0,0,1},{1,0,0,1}}
Output
2
