2010年1月31日星期日.ural1060-pku1753
Neerc2000中的一题。
题目要求:
给出一个4×4的棋盘的黑白状态，求最少需要多少次翻转(每次翻转会改变当前格和周围四个格的
状态),使棋盘变成全黑或者全白。
貌似是这套题中最水的一题，分析一下复杂度，发现即使完全枚举状态，复杂度也是可以接受的，
然后就枚举吧。
我的存储方法是用一个int型表示棋盘状态，黑1白0,将四行按顺序连起来，写成一个16位整数。
1
2 const int inf = 0x7fffffff;
3 #define bin(x) (1 <<(x))
4 int mask = bin(16) - 1;
5 int addr(const int &x,const int &y)
6 { return x * 4 + y; }
7 int grid;
8 //http://www.cppblog.com/schindlerlee
9 bool flip(int press)
10 {
11 int g = grid,i;
12 for (i = 0;i < 16;i++) {
13 if(press & bin(i)) {
14 g ^= bin(i);
15 g ^= bin(i + 4);
16 g ^= bin(i - 4);
17 if (i != 3 && i!= 7 && i != 11 && i!= 15) { g ^= bin(i+1); }
18 if (i != 0 && i!= 4 && i != 8 && i!= 12) { g ^= bin(i-1); }
19 }
20 }
21 g &= mask;
22 return (g == 0) || (g == mask);
23 }
24
25 int count(int x)
26 {
27 int res = 0;
28 while(x > 0) {
29 res += x & 1;
30 x >>= 1;
31 }
32 return res;
33 }
34
35 void ckmin(int & res,int x) { if(x < res) res = x; }
36 int main()
37 {
38 char s[16];
39 int i,j;
40 for (i = 0;i < 4;i++) {
41 scanf("%s\n",s);
42 for (j = 0;j < 4;j++) {
43 if(s[j] == 'b') {
44 grid |= bin(addr(i,j));
45 }
46 }
47 }
48
49 int res = inf;
50 for (i = 0;i <= mask;i++) {
51 if (flip(i)) {
52 //printf("i=%d\n",i);
53 ckmin(res,count(i));
54 }
55 }
56 if(res == inf) {
57 printf("Impossible\n");
58 }else {
59 printf("%d\n",res);
60 }
61 return 0;
62 }
63