2834076_ac_670ms_152k.c

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>

int x[10], f[10];
int turn[10][10] = {{0},{1,2,4,5,0},{1,2,3,0},{2,3,5,6,0},{1,4,7,0},{2,4,5,6,8,0},{3,6,9,0},{4,5,7,8,0},{7,8,9,0},{5,6,8,9,0}};

int check()
{
	int i, j;
	int t[10];

	for(i = 1; i < 10; i++)
		t[i] = f[i];
	for(i = 1; i < 10; i++)
	{
		for(j = 0; turn[i][j]; j++)
			t[turn[i][j]] += x[i];
	}
	for(i = 1; i < 10; i++)
		if(t[i]%4)
			return 0;
	return 1;
}

void cpy(char tmp[])
{
	int i, j, len;

	len = 0;
	for(i = 1; i < 10; i++)
	{
		for(j = 0; j < x[i]; j++)
			tmp[len++] = i+'0';
	}
	tmp[len] = '\0';
}

int main()
{
	int i, sum, ans;
	char tmp[30], out[30];

	for(i = 1; i < 10; i++)
		scanf("%d",&f[i]);
	ans = 10000;
	for(x[1] = 0; x[1] < 4; x[1]++)
	for(x[2] = 0; x[2] < 4; x[2]++)
	for(x[3] = 0; x[3] < 4; x[3]++)
	for(x[4] = 0; x[4] < 4; x[4]++)
	for(x[5] = 0; x[5] < 4; x[5]++)
	for(x[6] = 0; x[6] < 4; x[6]++)
	for(x[7] = 0; x[7] < 4; x[7]++)
	for(x[8] = 0; x[8] < 4; x[8]++)
	for(x[9] = 0; x[9] < 4; x[9]++)
	{
		sum = x[1]+x[2]+x[3]+x[4]+x[5]+x[6]+x[7]+x[8]+x[9];
		if(check())
		{
			if(sum<ans)
			{
				ans = sum;
				cpy(tmp);
				strcpy(out,tmp);
			}
			else
				if(sum==ans)
				{
					cpy(tmp);
					if(strcmp(tmp,out)<0)
						strcpy(out,tmp);
				}
		}
	}
	for(i = 0; tmp[i]!='\0'; i++)
		printf("%c ",out[i]);
	printf("\n");
	return 0;
}