下次遇见这种题还是暴利枚举第一行好了……
贴一下我调了五个小时的高斯消元+枚举自由变量：
真心要吐了……
#include <iostream>
using namespace std;
#define SIZE 20
#define N 16
#define INF (1<<20)
bool a[SIZE][SIZE]={0},isfree[SIZE]={0},x[SIZE]={0};	//isfree[i]表示x[i]为自由元
int pivot[SIZE]={0},freex[SIZE]={0},r[SIZE]={0};
		//pivot[i]是第i个主元所在的列，r[i]为其所在的行;freex[i]是第i个自由元所在的列
char board[SIZE][SIZE];

int Gauss(int s)
{
	int i,j,k,index,col,p,f,cnt;
	bool tmp;

	for (i=0;i<N;i++)
		for (j=0;j<N;j++)
			a[i][j]=0;

	for (i=0;i<4;i++)			//构造系数矩阵A
		for (j=0;j<4;j++)
		{
			k = 4*i+j;
			a[k][k]=1;
			if (i>0)		a[k][k-4]=1;		//上
			if (i<3)		a[k][k+4]=1;		//下
			if (j>0)		a[k][k-1]=1;		//左
			if (j<3)		a[k][k+1]=1;		//右
			a[k][N] = (board[i][j]=='b')^s;
		}

	for (p=f=k=col=0; k<N && col<N; k++,col++)		//消元
	{
		for (i=k; i<N && !a[i][col]; i++);
		if ( (index=i)==N )	{k--;isfree[col]=true;freex[f++]=col;continue;}

		isfree[col] = false;
		pivot[p] = col;
		r[p++] = k;

		if (index!=k)
			for (j=col;j<=N;j++)
				{tmp=a[k][j];a[k][j]=a[index][j];a[index][j]=tmp;}

		for (i=k+1;i<N;i++)
			if (a[i][col])
				for (j=col;j<=N;j++)
					a[i][j] ^= a[k][j];
	}

	for (i=k;i<N;i++)			//判定无解
		if (a[i][N])	return INF;

	int tot= (1<<f);
	int res = INF;
	for (k=0;k<tot;k++)		//枚举自由变量的取值。无自由元时也可以统一进来
	{
		index = k;			//自由变量取遍k的每一个二进制位
		cnt = 0;
		for (j=0;j<f;j++)	
		{
			x[freex[j]] = (index & 1);
			if (x[freex[j]])		cnt++;
			index>>=1;
		}

		for (i=p-1;i>=0;i--)		//回代求得每一个（共p个）主元的值
		{
			x[r[i]] = a[r[i]][N];
			for (j=N-1; j>pivot[i]; j--)
				if (a[r[i]][j])		x[r[i]] ^= x[j];
			if (x[r[i]])	cnt++;

		}
		if (cnt<res)	res=cnt;
	}

	return res;
}

int main()
{
	int i,j,tmp,ans=INF;
	for (i=0;i<4;i++)
		for (j=0;j<4;j++)
			cin >> board[i][j];

	if ( (tmp=Gauss(0))<ans )		ans=tmp;
	if ( (tmp=Gauss(1))<ans )		ans=tmp;
	if (ans!=INF)
		cout << ans << endl;
	else
		cout << "Impossible" << endl;
	
	return 0;
}

• Re:给高斯消元跪了…… (237) troore 2013-02-26 17:22:41