本文共 1844 字，大约阅读时间需要 6 分钟。
题目地址：http://poj.org/problem?id=1753
1 /* 2 这题几乎和POJ 2965一样，DFS函数都不用修改 3 只要修改一下change规则。。。 4 注意：是否初始已经ok了要先判断 5 */ 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 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\n", 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\n", 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 Impossible103 */
转载于:https://www.cnblogs.com/Running-Time/p/4372140.html