pku1166.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>

int mv[9];
int sa[9];
int min;
int ans[9];

int M[9][9] = 
	{
		{1, 1, 0, 1, 1, 0, 0, 0, 0},
		{1, 1, 1, 0 ,0, 0, 0, 0, 0},
		{0, 1, 1, 0, 1, 1, 0, 0, 0},
		{1, 0, 0, 1, 0, 0, 1, 0, 0},
		{0, 1, 0, 1, 1, 1, 0, 1, 0},
		{0, 0, 1, 0, 0, 1, 0, 0, 1},
		{0, 0, 0, 1, 1, 0, 1, 1, 0},
		{0, 0, 0, 0, 0, 0, 1, 1, 1},
		{0, 0, 0, 0, 1, 1, 0, 1, 1},
	};

int Test()
{
	int i, j;
	int cg[9];
	for (i = 0; i < 9; i++)
	{
		cg[i] = 0;
		for (j = 0; j < 9; j++)
		{
			cg[i] += M[j][i] * mv[j];
		}
		if ((cg[i] + sa[i]) % 4)
		{
			return 0;
		}
	}
	return 1;
}

void DFS(int id)
{
	int i, sum;

	if (id == 9)
	{
		for (i = 0, sum = 0; i < 9; i++)
		{
			sum += (mv[i] == 0) ? 0 : 1;
		}
		if (sum >= min)
		{
			return;
		}
		if (Test())
		{
			min = sum;
			for (i = 0; i < 9; i++)
			{
				ans[i] = mv[i];
			}
		}
		return;
	}

	for (i = 0; i < 4; i++)
	{
		mv[id] = i;
		DFS(id + 1);
	}
}

void Solve()
{
	int i;
	min = 100;
	DFS(0);
	for (i = 0; i < 9; i++)
	{
		while (ans[i]--)
		{
			printf("%d ", i + 1);
		}
	}
	printf("\n");
}

int main()
{
	int i;
	for (i = 0; i < 9; i++)
	{
		scanf("%d", &sa[i]);
	}
	Solve();
	return 0;
}