题目地址：http://poj.org/problem?id=1753
1 /*
2 这题几乎和POJ 2965一样，DFS函数都不用修改
3 只要修改一下change规则。。。
4 注意：是否初始已经ok了要先判断
5 */
6 #include <cstdio>
7 #include <iostream>
8 #include <algorithm>
9 #include <cstring>
10 #include <cmath>
11 #include <string>
12 #include <map>
13 #include <queue>
14 #include <vector>
15 using namespace std;
16
17 const int MAXN = 1e6 + 10;
18 const int INF = 0x3f3f3f3f;
19 int a[5][5];
20 bool flag;
21
22 bool ok(void)
23 {
24 int tmp = a[1][1];
25 for (int i=1; i<=4; ++i)
26 {
27 for (int j=1; j<=4; ++j)
28 if (a[i][j] != tmp) return false;
29 }
30
31 return true;
32 }
33
34 void change(int x, int y)
35 {
36 a[x][y] = !a[x][y];
37 if (x > 1) a[x-1][y] = !a[x-1][y];
38 if (x < 4) a[x+1][y] = !a[x+1][y];
39 if (y > 1) a[x][y-1] = !a[x][y-1];
40 if (y < 4) a[x][y+1] = !a[x][y+1];
41 }
42
43 void DFS(int x, int y, int num, int cnt)
44 {
45 if (num == cnt)
46 {
47 flag = ok ();
48 return ;
49 }
50 for (int i=x; i<=4; ++i)
51 {
52 int j;
53 if (i == x) j = y + 1;
54 else j = 1;
55 for (; j<=4; ++j)
56 {
57 change (i, j);
58 DFS (i, j, num+1, cnt);
59 if (flag) return ;
60 change (i, j);
61 }
62 }
63 }
64
65 void work(void)
66 {
67 if (ok ())
68 {
69 printf ("%d
", 0); return ;
70 }
71 int cnt;
72 for (cnt=1; cnt<=16; ++cnt) //最多16次，可以暴力枚举
73 {
74 flag = false;
75 DFS (1, 0, 0, cnt);
76 if (flag) break;
77 }
78 (cnt <= 16) ? printf ("%d
", cnt) : puts ("Impossible");
79 }
80
81 int main(void) //POJ 1753 Flip Game
82 {
83 //freopen ("A.in", "r", stdin);
84
85 char ch;
86 for (int i=1; i<=4; ++i)
87 {
88 for (int j=1; j<=4; ++j) //b-0 w-1
89 {
90 scanf ("%c", &ch);
91 a[i][j] = (ch == 'b') ? 0 : 1;
92 }
93 getchar ();
94 }
95
96 work ();
97
98 return 0;
99 }
100
101 /*
102 Impossible
103 */