2010年1月31日星期日.ural1060-pku1753
Neerc2000中的一題。
題目要求:
給出一個4×4的棋盤的黑白狀態(tài)，求最少需要多少次翻轉(zhuǎn)(每次翻轉(zhuǎn)會改變當前格和周圍四個格的
狀態(tài)),使棋盤變成全黑或者全白。
貌似是這套題中最水的一題，分析一下復雜度，發(fā)現(xiàn)即使完全枚舉狀態(tài)，復雜度也是可以接受的，
然后就枚舉吧。
我的存儲方法是用一個int型表示棋盤狀態(tài)，黑1白0,將四行按順序連起來，寫成一個16位整數(shù)。
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.shnenglu.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