2676.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Problem Id:2676  User Id:fzk 
#include <stdio.h>
#include <algorithm>
#include <memory.h>
#include <math.h>
using namespace std;
int sign[9][9][10];
int s[9][9];
char map[10][10];
char map2[10][10];
struct point
{
	int x, y;
}p[100];
bool cmp( point a, point b )
{
	return s[a.x][a.y] < s[b.x][b.y];
}
bool set( int i, int j, int t, int key )
{
	int a, b, x, y, k;
	bool ans = true;

	for( x = a = i/3*3; x < a + 3; x++ )
	for( y = b = j/3*3; y < b + 3; y++ )
	if( x != i || y != j )
	{
		if( sign[x][y][t] == 0 && key == 1 )
			s[x][y]--;
		if( sign[x][y][t] == 1 && key == -1 )
			s[x][y]++;
		sign[x][y][t]+=key;
		if( s[x][y] == 0 )
			ans = false;
	}
	for( k=0; k<9; k++ )
	{
		if( k != j )
		{
			if( sign[i][k][t] == 0 && key == 1 )
				s[i][k] --;
			if( sign[i][k][t] == 1 && key == -1 )
				s[i][k] ++;
			sign[i][k][t]+=key;
			if( s[i][k] == 0 )
				ans = false;
		}
		if( k != i )
		{
			if( sign[k][j][t] == 0 && key == 1 )
				s[k][j] --;
			if( sign[k][j][t] == 1 && key == -1 )
				s[k][j] ++;
			sign[k][j][t]+=key;
			if( s[k][j] == 0 )
				ans = false;
		}

	}
	return ans;
}
void init( )
{
	int i, j;
	memset( sign, 0, sizeof sign );

	for( i=0; i<9; i++ )
		scanf( "%s", map[i] );

	for( i=0; i<9; i++ )
	for( j=0; j<9; j++ )
	{
		s[i][j] = 9;
		p[i*9+j].x = i;
		p[i*9+j].y = j;
	}
	for( i=0; i<9; i++ )
	for( j=0; j<9; j++ )
	if( map[i][j] != '0' )
		set( i, j, map[i][j]-'0', 1 );
}
bool search( int a )
{
	int i = p[a].x, j = p[a].y, k;
	if( a == 9*9 )
		return true;
	if( map[i][j] != '0' )
		return search( a + 1 );	
	for( k=1; k<10; k++ )
		if( sign[i][j][k] == 0 )
		{
			map2[i][j] = k+'0';

			if( set( i, j, k, 1 ) && search( a+1 ) )
				return true;
			set( i, j, k, -1 );
		}

	return false;
}
int main( )
{
	int cas, i, j;
	scanf( "%d", &cas );
	while( cas-- )
	{
		init( );
		sort( p, p+9*9, cmp );
		search( 0 );

		for( i=0; i<9; i++ )
		{
			for( j=0; j<9; j++ )
			{
				if( map[i][j] != '0' )
					printf( "%c", map[i][j] );
				else
					printf( "%c", map2[i][j] );
			}
			printf( "\n" );
		}
	}
	return 0;
}