位运算+搜索
题意：将下图这样的图案都变成减号，规则每次改变一个，这一个的行和列都会发生转换；
思路：总共有2^16的情况，全部都搜一遍，用位运算一次改变一行和一列；
-+--
----
----
-+--
搜索题解：
View Code #include#include #include #include using namespace std; int result = 17; int path = 0; int s[16] = { 0xf888,0xf444,0xf222,0xf111, 0x8f88,0x4f44,0x2f22,0x1f11, 0x88f8,0x44f4,0x22f2,0x11f1, 0x888f,0x444f,0x222f,0x111f }; int num = 0; void search(int d,int step,int q) { if( step >= result) return; if(d >= 16) { if(step < result && 0 == num) { result = step; path = q; } return ; } q= q << 1; q++; num = num ^ s[d]; search(d + 1, step+1, q); num = num ^ s[d]; q--; search(d + 1, step, q); q = q >>1; } void output() { int bit = 15; printf("%d\n",result); for(int i = 1; i <= 4; ++i) for(int j = 1; j <= 4; ++j) { if((path >> bit)&1) printf("%d %d\n",i,j); bit--; } } int main() { char a; for(int i = 0;i < 16; ++i) { a=getchar(); if('+' == a || '-' == a) { num = num << 1; if('+' == a) num++; } else i--; } search(0,0,0); output(); return 0; }
简便题解：
View Code #include#include #include #include #include using namespace std; int map[4][4] = { 0}; int ji[4][4] = { 0}; void bian(int a,int b) { for(int i = 0;i < 4;++i) map[a][i] = !map[a][i]; for(int i = 0;i <4;++i) map[i][b] = !map[i][b]; } int main() { char a; for(int i = 0;i < 4;++i) { for(int j =0;j < 4 ;++j) { scanf("%c",&a); if('+' == a) map[i][j] = 1; } getchar(); } for(int i = 0;i < 4;++i) for(int j= 0;j < 4; ++j) if(1 == map[i][j]) ji[i][j] = 1; for(int i = 0;i < 4;++i) for(int j = 0;j < 4;++j) if(ji[i][j]) bian(i,j); int num = 0; for(int i = 0;i <4;++i) for(int j = 0;j <4;++j) if(map[i][j]) ++num; printf("%d\n",num); for(int i = 0;i <4;++i) for(int j = 0;j <4;++j) if(map[i][j]) printf("%d %d\n",i+1,j+1); return 0; }