2299717_tle.cc

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

#include <stdio.h>
#include <string.h>
#define C 45
int over;
int pp, sud[10][10];
int stack[82][2];
int r[10][10], c[10][10], s[10][10];

int f(int i, int j)
{
	i = (i-1)/3;
	j = (j-1)/3+1;
	return i*3+j;
}

void output()
{
	int i, j;
	
	for(i = 1; i <= 9; i++)
		for(j = 1; j <= 9; j++)
			printf("%d",sud[i][j]);
	printf("\n");
}

void solve(int n)
{
	int i, j, k;
	int F, tmp[9];

	i = stack[n][0], j = stack[n][1];
	F = 0;
	for(k = 1; k <= 9; k++)
	{
		if(r[i][k]==0&&c[j][k]==0&&s[f(i,j)][k]==0)
			tmp[F++] = k;
	}
	if(!F)
		return ;
	if(n==pp-1&&F==1)
	{
		over = 1;
		sud[i][j] = tmp[0];
		output();
		return ;
	}
	for(k = F-1; k >= 0; k--)
	{
		sud[i][j] = tmp[k];
		r[i][tmp[k]] = c[j][tmp[k]] = s[f(i,j)][tmp[k]] = 1;
		solve(n+1);
		if(over)
			return ;
		sud[i][j] = 0;
		r[i][tmp[k]] = c[j][tmp[k]] = s[f(i,j)][tmp[k]] = 0;
	}
}

void pre_solve()
{
	int i, j, p, tmp, P, J;
	int mark = 1, con;

	while(mark)
	{
		mark = 0;
		for(j = 1; j <= 9; j++)
		{
			tmp = 0;
			for(p = 1; p <= 9; p++)
				if(sud[j][p]=='0')
				{
					tmp++;
					P = p;
				}
			if(tmp==1)
			{
				con = C;
				for(p = 0; p < 9; p++)
					con -= sud[j][p];
				sud[j][P] = con;
				mark = 1;
			}
		}
		for(p = 0; p < 9; p++)
		{
			tmp = 0;
			for(j = 0; j < 9; j++)
				if(sud[j][p]=='0')
				{
					tmp++;
					J = j;
				}
			if(tmp==1)
			{
				con = C;
				for(j = 0; j < 9; j++)
					con -= sud[j][p];
				sud[J][p] = con;
				mark = 1;
			}
		}
		for(j = 0; j < 9; j+=3)
		{
			for(p = 0; p < 9; p+=3)
			{
				tmp = 0;con = C;
				if(sud[j][p+0]=='0') {tmp++;J = j;P = p+0;} else con -= sud[j][p+0];
				if(sud[j][p+1]=='0') {tmp++;J = j;P = p+1;} else con -= sud[j][p+1];
				if(sud[j][p+2]=='0') {tmp++;J = j;P = p+2;} else con -= sud[j][p+2];
				if(sud[j+1][p]=='0') {tmp++;J = j+1;P = p;} else con -= sud[j+1][p];
				if(sud[j+1][p+1]=='0') {tmp++;J = j+1;P = p+1;} else con -= sud[j+1][p+1];
				if(sud[j+1][p+2]=='0') {tmp++;J = j+1;P = p+2;} else con -= sud[j+1][p+2];
				if(sud[j+2][p+0]=='0') {tmp++;J = j+2;P = p+0;} else con -= sud[j+2][p+0];
				if(sud[j+2][p+1]=='0') {tmp++;J = j+2;P = p+1;} else con -= sud[j+2][p+1];
				if(sud[j+2][p+2]=='0') {tmp++;J = j+2;P = p+2;} else con -= sud[j+2][p+2];
				if(tmp==1)
				{
					sud[J][P] = con;
						mark = 1;
				}
			}
		}
	}
	for(i = 1; i <= 9; i++)
		for(j = 1; j <= 9; j++)
			if(sud[i][j]==0)
				stack[pp][0] = i,stack[pp++][1] = j;
			else
			{
				p = sud[i][j];
				r[i][p] = 1, c[j][p] = 1, s[f(i,j)][p] = 1;
			}
}

int input()
{
	int i, j, t;
	char ch[82];

	scanf("%s",ch);
	if(ch[0]=='e')
		return 0;
	pp = over = 0;
	memset(r,0,sizeof(r));
	memset(c,0,sizeof(c));
	memset(s,0,sizeof(s));
	for(i = 1; i <= 9; i++)
	{
		for(j = 1; j <= 9; j++)
		{
			t = (i-1)*9+j-1;
			if(ch[t]=='.')
				ch[t] = '0';
			sud[i][j] = ch[t]-'0';
		}
	}
	pre_solve();
	solve(0);
	return 1;
}

int main()
{
	while(input());
	return 1;
}