题目描述
kkke在一个n*n的棋盘上进行一个翻转游戏。棋盘的每个格子上都放有一个棋子，每个棋子有2个面，一面是黑色的，另一面是白色的。初始的时候，棋盘上的棋子有的黑色向上，有的白色向上。现在kkke想通过最少次数的翻转，使得棋盘上所有的棋子都是同一个颜色向上的（即全是黑色向上的，或全是白色向上的）。每次翻转的时候，kkke可以选择任意一个棋子，将它翻转，同时，与它上下左右分别相邻的4个棋子也必须同时翻转。
输入输出格式
输入格式：
输入的第一行是一个整数n，表示棋盘是n*n的，
接下来有n行，每行包括n个字母，表示初始的棋盘状态。如果字母是w，则表示这个棋子当前是白色向上的，如果字母是b，则表示这个棋子当前是黑色向上的。
输出格式：
输出为一行，如果无法翻转出目标状态，则输出“Impossible”，否则输出一个整数，表示kkke最少需要翻转的次数。
输入输出样例
输入样例#1:
4
bwwb
bbwb
bwwb
bwww
输出样例#1:
4
说明
【数据范围】
对于30%的数据，1<=n<=4
对于100%的数据，1<=n<=16
题解
看到这一题， 我试了试 IDA*, 看看能水几分， 没想到只能水30， 果断滚粗。
直接爆搜显然是会TLE 的， 那么只能考虑其他办法。
那么我们枚举第一行的翻转， 并把翻转后的图记录， 进行第二行的搜索。
由于第一行已经不能再翻， 如果第一行存在没有达到目标 颜色的棋子，只能由第二行来翻转。
所以可以根据第一行的颜色 来 给第二行进行翻转， 并且可能性仅一种。
这样一直翻转到最后一行结束， 那么除了最后一行 其他棋子 一定达到了目标颜色。
最后再判断最后一行棋子是否都达到了目标颜色， 如果达到了就更新答案。
代码
原谅我丑的不行的代码
#include<cstring>
#include<algorithm>
#include<cstdio>
#define rep(i,a,b) for( int i = (a); i <= (b); ++i )
#define per(i,a,b) for( int i = (a); i >= (b); --i )
using namespace std; const int N = , inf = ~0U >> ; int n, mp[N][N], ans, tmp[N][N];
char s[N]; int cal( int x , int pos ) {
return (x >> pos) & ;
} int work( int re , int col) {
rep( i, , n - ) rep( j, , n - ) if( tmp[i - ][j] != col ){
re++;
tmp[i][j] ^= ;
tmp[i + ][j] ^= ;
if(j) tmp[i][j - ] ^= ;
if(j != n - ) tmp[i][j + ] ^= ;
}
rep( j, , n - ) if( tmp[n - ][j] != col ) return inf;
return re;
} int dfs() {
int re = inf;
rep( i, , ( << n) - ) rep( col, , ){
rep( j, , n - ) rep( k, , n - ) tmp[j][k] = mp[j][k];
int cnt = ;
rep( j, , n - ) if( cal( i, j ) ) cnt++;
rep( j, , n - ) if( cal( i, j ) ^ cal( i , j - ) ^ cal( i, j + ) ) tmp[][j] ^= ;
rep( j, , n - ) if( cal( i, j ) ) tmp[][j] ^= ;
re = min( re, work(cnt, col) );
}
return re;
} int main()
{
scanf("%d",&n);
rep( i, , n - ) {
scanf("%s",s);
rep( j, , n - ) mp[i][j] = s[j] == 'w';
}
ans = dfs();
if( ans == inf ) printf("Impossible\n");
else printf("%d\n", ans);
}