题目地址&＃xff1a;http://poj.org/problem?id&＃61;1753
1 /* 2 这题几乎和POJ 2965一样&＃xff0c;DFS函数都不用修改 3 只要修改一下change规则。。。 4 注意&＃xff1a;是否初始已经ok了要先判断 5 */ 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include <string> 12 #include 13 #include 14 #include 15 using namespace std; 16 17 const int MAXN &＃61; 1e6 &＃43; 10; 18 const int INF &＃61; 0x3f3f3f3f; 19 int a[5][5]; 20 bool flag; 21 22 bool ok(void) 23 { 24 int tmp &＃61; a[1][1]; 25 for (int i&＃61;1; i<&＃61;4; &＃43;&＃43;i) 26 { 27 for (int j&＃61;1; j<&＃61;4; &＃43;&＃43;j) 28 if (a[i][j] !&＃61; tmp) return false; 29 } 30 31 return true; 32 } 33 34 void change(int x, int y) 35 { 36 a[x][y] &＃61; !a[x][y]; 37 if (x > 1) a[x-1][y] &＃61; !a[x-1][y]; 38 if (x <4) a[x&＃43;1][y] &＃61; !a[x&＃43;1][y]; 39 if (y > 1) a[x][y-1] &＃61; !a[x][y-1]; 40 if (y <4) a[x][y&＃43;1] &＃61; !a[x][y&＃43;1]; 41 } 42 43 void DFS(int x, int y, int num, int cnt) 44 { 45 if (num &＃61;&＃61; cnt) 46 { 47 flag &＃61; ok (); 48 return ; 49 } 50 for (int i&＃61;x; i<&＃61;4; &＃43;&＃43;i) 51 { 52 int j; 53 if (i &＃61;&＃61; x) j &＃61; y &＃43; 1; 54 else j &＃61; 1; 55 for (; j<&＃61;4; &＃43;&＃43;j) 56 { 57 change (i, j); 58 DFS (i, j, num&＃43;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&＃61;1; cnt<&＃61;16; &＃43;&＃43;cnt) //最多16次&＃xff0c;可以暴力枚举 73 { 74 flag &＃61; false; 75 DFS (1, 0, 0, cnt); 76 if (flag) break; 77 } 78 (cnt <&＃61; 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&＃61;1; i<&＃61;4; &＃43;&＃43;i) 87 { 88 for (int j&＃61;1; j<&＃61;4; &＃43;&＃43;j) //b-0 w-1 89 { 90 scanf ("%c", &ch); 91 a[i][j] &＃61; (ch &＃61;&＃61; &＃39;b&＃39;) ? 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
京公网安备 11010802041100号