题目传送门 http://poj.org/problem?id=1753
题意描述
有 \(4 \times 4\)的正方形, 每个格子要么是黑色, 要么是白色, 当把一个格子的颜色改变 (黑 \(\to\) 白 或 白 \(\to\)黑)时, 其周围上下左右 (如果存在的话) 的格子的颜色也被反转, 问至少反转几个格子可以使 \(4 \times 4\)的正方形变为纯白或者纯黑?
分析
对于每一个格子, 只有两个状态, 将它翻转一次与翻转奇数次效果是一样的, 翻转零次与翻转偶数次的效果是一样的.
因为只有 \(16\)个格子, 选择 \(0\)个,\(1\)个,\(2\)个 \(\cdots16\)个所有的情况有
C[0][16]+C[1][16]+C[2][16]+...+C[15][16]+C[16][16]=2^16
枚举不会超时, 所以我们可以用递归的思想模拟 0-16 重循环, 分别表示选择翻转的棋子个数.
AC 代码
- #include<iostream>
- #include<algorithm>
- #include<cstdio>
- #include<cstring>
- #include<cmath>
- using namespace std;
- bool bits[16], flag=false;
- inline void resever(int n) {// 翻转
- int x=n/4,y=n%4;
- for (int i=max(0,y-1); i<min(y+2,4); i++)
- bits[x*4+i]=!bits[x*4+i];
- if (x!=0) bits[(x-1)*4+y]=!bits[(x-1)*4+y];
- if (x!=3) bits[(x+1)*4+y]=!bits[(x+1)*4+y];
- }
- inline bool judge() {// 判断是否一致
- bool INI=bits[0];
- for (int i=1; i<16; i++)
- if (INI!=bits[i]) return 0;
- return 1;
- }
- inline void solve(int maxx, int now, int step) {
- if (maxx==step) {// 翻转完最后一枚棋子
- if (judge()) {// 满足状态
- flag=1;
- printf("%d\n",maxx);
- }
- return ;
- }
- for (int i=now; i<16; i++) {// 从上次翻转位置继续
- resever(i);// 翻转 i
- solve(maxx, i+1, step+1);
- if (flag) return ;// 找到答案, 返回
- resever(i);// 恢复原来状态
- }
- }
- int main() {
- char str[4][4];
- for (int i=0; i<4; i++) {
- cin>>str[i];
- for (int j=0; j<4; j++)
- bits[i*4+j]=(str[i][j]=='b') ? 1 : 0;
- }
- for (int i=0; i<=16; i++)//i 为要翻转的棋子个数
- solve(i, 0, 0);
- if (!flag) printf("Impossible\n");// 没有找到答案
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2893755.html