2299673_ac_671ms_68k.cc

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

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

int over;
int p, 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==p-1&&F==1)
	{
		over = 1;
		sud[i][j] = tmp[0];
		output();
		return ;
	}
	for(k = 0; k < F; 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 input()
{
	int i, j;
	char ch;

	p = over = 0;
	memset(r,0,sizeof(r));
	memset(c,0,sizeof(c));
	memset(s,0,sizeof(s));
	for(i = 1; i <= 9; i++)
	{
		getchar();
		for(j = 1; j <= 9; j++)
		{
			scanf("%c",&ch);
			sud[i][j] = ch-'0';
			if(ch=='0')
				stack[p][0] = i,stack[p++][1] = j;
			else
				r[i][ch-'0'] = 1, c[j][ch-'0'] = 1, s[f(i,j)][ch-'0'] = 1;
		}
	}
	solve(0);
}

int main()
{
	int n;

	scanf("%d",&n);
	while(n--)
		input();
	return 1;
}