题目大意：
一个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 }
与上题基本相同，只不过需要一个栈来记录翻转的坐标。
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\n", i); 70 while (!s.empty()) { 71 printf("%d", s.top()); 72 s.pop(); 73 printf(" %d\n", s.top()); 74 s.pop(); 75 } 76 return 0; 77 }
原文：https://www.cnblogs.com/lxc1910/p/10489212.html