Luogu P1764 / POJ 1753

#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int M=16;
int n,ans;
int g[M][M],k[M][M];

void Init(){
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			k[i][j]=g[i][j];
}

int Solve(int a){
	int cal=1<<n;
	int cnt,sum=0x3f3f3f3f;
	for(int h=0;h<cal;h++){
		Init();
		cnt=0;
		bool flag=true;
		for(int i=0;i<n;i++)
		{
			if(h&(1<<i)) continue;
			cnt++;
			k[0][i]=1-k[0][i],k[1][i]=1-k[1][i];
			if(i>0)	k[0][i-1]=1-k[0][i-1];
			if(i<n-1) k[0][i+1]=1-k[0][i+1];
		}
	    for(int i=1;i<n;i++)
	    	for(int j=0;j<n;j++)
	    		if(k[i-1][j]!=a){
	    			cnt++;
	    			k[i][j]=1-k[i][j];
	    			k[i+1][j]=1-k[i+1][j];
	    			if(j>0) k[i][j-1]=1-k[i][j-1];
	    			if(j<n-1) k[i][j+1]=1-k[i][j+1];
				}
		for(int i=0;i<n;i++)
			if(k[n-1][i]!=a)
				flag=false;
		if(flag&&cnt<sum) sum=cnt;
	}		
	return sum;
}

int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("\n");
		for(int j=0;j<n;j++){
			char tmp;
			scanf("%c",&tmp);
			if(tmp=='b') g[i][j]=1;
			else g[i][j]=0;
		}
	}
	if(n==1){
		puts("0");
		return 0;
	}
	ans=min(Solve(1),Solve(0));
	if(ans==0x3f3f3f3f) printf("Impossible\n");
	else printf("%d\n",ans);
	return 0;
}