该题就是和“最短Hamilton路径” 这个题很像,直接遍历1~1<<16位就好了
注意:该题同一个位置转换两次是没有意义的,无论同一个点放置的位置如何,都是可以抵消的,所以每个点只需要操作一次。
#include<iostream>
using namespace std;
int arr[6][6];
int temp[6][6];
char ch;
void solve(int point){
int y = point / 4, x = point - 4 * y;
for(int i = 0; i < 4; i ++){
temp[y][i] ^= 1; // 用位运算的方式进行转换
temp[i][x] ^= 1;
}
temp[y][x] ^= 1; // 同一个点进行两次转换,就算没有进行转换,那么就需要再进行一次转换
}
bool check(){
for(int i = 0; i < 4; i++)
for(int j = 0; j < 4; j++)
if(temp[i][j] == 1)
return false;
return true;
}
void init(){
for(int k = 0; k < 4; k++)
for(int j = 0;j < 4; j++)
temp[k][j] = arr[k][j];
}
int main (void){
for(int i = 0; i < 4; i++)
for(int j = 0;j < 4; j++){
cin >> ch;
arr[i][j] = (ch == '+' ? 1 : 0); // 将+,-转换为1,0状态,便于转换
}
for(int i = 0; i < (1 << 16); i++){
int temp1 = i;
int x = 0;
init();
while(temp1){
if(temp1 & 1) solve(x); // 如果需要转换该位就进行转换
temp1 >>= 1; x++;
}
if(check()) {
int x = i, sum = 0;
while(x){ // 统计1 的个数
if(x & 1) sum ++;
x >>= 1;
}
cout << sum << endl;
x = 0;
while(i){
if(i & 1) cout << x / 4 + 1 << " " << x % 4 + 1 << endl;
x++; i >>= 1;
}
break;
}
}
return 0;
}