poj 1753、2965枚举

题目大意：

一个4乘4的棋盘，上面放满了正反两面分别为黑和白的棋子，翻转一个棋子会让这个棋子上下左右的棋子也翻转，给定一个初始状态，求使所有棋子颜色相同所需的最少翻转次数。

解题思路：

先检查翻转0个棋子时是否所有棋子颜色一致，若不一致则翻转1个棋子，依次类推，若翻转某n个棋子后成功则n即为所求解，否则直到翻转16个棋子后仍未成功则输出“Impossible”。

翻转某n个棋子可用递归的方法，若递归函数中当前层翻转的是(i, j)，则下一层递归函数从(i, j+ 1)开始选择，这样可以保证不重复。若j等于4（说明第i行已结束，）则应让j = 0; i++；到下一行中搜索。

用一个一维数组board[6]代表棋盘，其中board[i]（i >= 1 && i <= 4）代表第i行，board[i]的二进制数最右边四位从左到右分别代表棋盘第i行的第1到4列。这样对棋子取反更方便。

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 
 5 int board[6];
 6 int state[2][4] = { { 8, 4, 2, 1 }, { 12, 14, 7, 3 } };
 7
 8 void read() {
 9     char c;
10     for (int i = 1; i <= 4; i++) {
11         for (int j = 1; j <= 4; j++) {
12             board[i] <<= 1;
13             cin >> c;
14             if (c == 'b')
15                 board[i] |= 1;
16         }
17     }
18 }
19 
20 bool judge() {
21     if (board[4] == 0 && board[1] == 0 && board[2] == 0 && board[3] == 0 ||
22         board[4] == 15 && board[1] == 15 && board[2] == 15 && board[3] == 15)
23         return true;
24     return false;
25 }
26 
27 void flip(int i, int j) {
28     i++; //下标从1开始
29     board[i] ^= state[1][j];
30     board[i - 1] ^= state[0][j];
31     board[i + 1] ^= state[0][j];
32 }
33 
34 bool work(int n, int i, int j) {//还有n个棋子需翻转
35     if (n == 0)
36         return judge();
37     if (j == 4) {
38         j = 0; i++;
39     }
40     if (4 - j + (3 - i) * 4 < n)
41         return false;
42     for (; i < 4; i++) {
43         for (; j < 4; j++) {
44             flip(i, j);
45             if(work(n - 1, i, j + 1))
46                 return true;
47             flip(i, j);
48         }
49         j = 0;
50     }
51     return false;
52 }
53 
54 int main() {
55     read();
56     int i;
57     for (i = 0; i <= 16; i++) {
58         if (work(i, 0, 0))
59             break;
60     }
61     if (i == 17)
62         cout << "Impossible" << endl;
63     else
64         cout << i << endl;
65     return 0;
66 }

2965题目链接

与上题基本相同，只不过需要一个栈来记录翻转的坐标。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <stack>
 4 using namespace std;
 5 
 6 int board[4];
 7 int state[4] = { 8, 4, 2, 1 };
 8 stack<int> s;
 9 
10 void read() {
11     char c;
12     for (int i = 0; i < 4; i++) {
13         for (int j = 0; j < 4; j++) {
14             board[i] <<= 1;
15             scanf_s("%c", &c);
16             if (c == '-')
17                 board[i] |= 1;
18         }
19         scanf_s("%c", &c); //读入换行符
20     }
21 }
22 
23 void change(int i, int j) {
24     for (int t = 0; t < 4; t++) {
25         if (t != i)
26             board[t] ^= state[j];
27     }
28     board[i] ^= 15;
29 }
30 
31 bool judge() {
32     for (int i = 0; i < 4; i++) {
33         if (board[i] != 15)
34             return false;
35     }
36     return true;
37 }
38 
39 bool work(int n, int i, int j) { //n为还需转换的个数
40     if (n == 0)
41         return judge();
42     if (j == 4) {
43         j = 0;
44         i++;
45     }
46     if (n > (4 - j) + (3 - i) * 4)
47         return false;
48     for (; i < 4; i++) {
49         for (; j < 4; j++) {
50             change(i, j);
51             if (work(n - 1, i, j + 1)) {
52                 s.push(j + 1); s.push(i + 1);
53                 return true;
54             }
55             change(i, j);
56         }
57         j = 0;
58     }
59     return false;
60 }
61 
62 int main() {
63     read();
64     int i, n = 0;
65     for (i = 0; i <= 16; i++) {
66         if (work(i, 0, 0))
67             break;
68     }
69     printf("%d
", i);
70     while (!s.empty()) {
71         printf("%d", s.top());
72         s.pop();
73         printf(" %d
", s.top());
74         s.pop();
75     }
76     return 0;
77 }