【HDU】2780 Su-Su-Sudoku【数独】精确覆盖

传送门：【HDU】2780 Su-Su-Sudoku【数独】

题目分析：

数独~

经典的精确覆盖问题。

这个月大概有100篇了。。（不包括莫名其妙变成这个月的从别的blog传送过来的博文。。。）

小小纪念一下~

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;

#define REP( i , a , b ) for ( int i = a ; i < b ; ++ i )
#define REV( i , a , b ) for ( int i = a - 1 ; i >= b ; -- i )
#define FOR( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define FOV( i , a , b ) for ( int i = a ; i >= b ; -- i )
#define REC( i , A , o ) for ( int i = A[o] ; i != o ; i = A[i] )
#define CLR( a , x ) memset ( a , x , sizeof a )

const int MAXN = 325 ;
const int MAXM = 730 ;
const int MAXNODE = 3000 ;
const int INF = 0x3f3f3f3f ;

struct DLX {
	int U[MAXNODE] , D[MAXNODE] , L[MAXNODE] , R[MAXNODE] ;
	int row[MAXNODE] , col[MAXNODE] ;
	int deep , ans[85] ;
	int H[MAXM] , S[MAXN] ;
	int n , m ;
	int size ;
	
	int G[10][10] ;
	
	void init () {
		CLR ( H , -1 ) ;
		FOR ( i , 0 , n ) {
			S[i] = 0 ;
			D[i] = i ;
			U[i] = i ;
			L[i] = i - 1 ;
			R[i] = i + 1 ;
		}
		L[0] = n ;
		R[n] = 0 ;
		size = n ;
	}
	
	void link ( int r , int c ) {
		++ size ;
		++ S[c] ;
		row[size] = r ;
		col[size] = c ;
		U[size] = U[c] ;
		D[size] = c ;
		D[U[c]] = size ;
		U[c] = size ;
		if ( ~H[r] ) {
			L[size] = L[H[r]] ;
			R[size] = H[r] ;
			L[R[size]] = size ;
			R[L[size]] = size ;
		}
		else
			H[r] = L[size] = R[size] = size ;
	}
	
	void remove ( int c ) {
		L[R[c]] = L[c] ;
		R[L[c]] = R[c] ;
		REC ( i , D , c )
			REC ( j , R , i ) {
				D[U[j]] = D[j] ;
				U[D[j]] = U[j] ;
				-- S[col[j]] ;
			}
	}
	
	void resume ( int c ) {
		REC ( i , U , c )
			REC ( j , L , i ) {
				++ S[col[j]] ;
				U[D[j]] = j ;
				D[U[j]] = j ;
			}
		R[L[c]] = c ;
		L[R[c]] = c ;
	}
	
	int dance ( int d ) {
		if ( R[0] == 0 ) {
			deep = d ;
			return 1 ;
		}
		int c = R[0] ;
		REC ( i , R , 0 )
			if ( S[c] > S[i] )
				c = i ;
		remove ( c ) ;
		REC ( i , D , c ) {
			ans[d] = row[i] ;
			REC ( j , R , i )
				remove ( col[j] ) ;
			if ( dance ( d + 1 ) )
				return 1 ;
			REC ( j , L , i )
				resume ( col[j] ) ;
		}
		resume ( c ) ;
		return 0 ;
	}
	
	void solve () {
		n = 9 * 9 * 4 ;
		init () ;
		REP ( i , 0 , 9 )
			REP ( j , 0 , 9 )
				scanf ( "%1d" , &G[i][j] ) ;
		REP ( i , 0 , 9 )
			REP ( j , 0 , 9 )
				if ( G[i][j] ) {
					int r = ( i * 9 + j ) * 9 + G[i][j] ;
					int c1 = i * 9 + j + 1 ;
					int c2 = 81 + i * 9 + G[i][j] ;
					int c3 = 162 + j * 9 + G[i][j] ;
					int c4 = 243 + ( i / 3 * 3 + j / 3 ) * 9 + G[i][j] ;
					link ( r , c1 ) ;
					link ( r , c2 ) ;
					link ( r , c3 ) ;
					link ( r , c4 ) ;
					S[c1] = S[c2] = S[c3] = S[c4] = -1 ;
				}
		REP ( i , 0 , 9 )
			REP ( j , 0 , 9 )
				if ( !G[i][j] )
					FOR ( k , 1 , 9 ) {
						int r = ( i * 9 + j ) * 9 + k ;
						int c1 = i * 9 + j + 1 ;
						int c2 = 81 + i * 9 + k ;
						int c3 = 162 + j * 9 + k ;
						int c4 = 243 + ( i / 3 * 3 + j / 3 ) * 9 + k ;
						if ( ~S[c1] && ~S[c2] && ~S[c3] && ~S[c4] ) {
							link ( r , c1 ) ;
							link ( r , c2 ) ;
							link ( r , c3 ) ;
							link ( r , c4 ) ;
						}
					}
		if ( !dance ( 0 ) )
			printf ( "Could not complete this grid.\n" ) ;
		else {
			REP ( i , 0 , deep ) {
				int Orz =  ( ans[i] - 1 ) % 9 + 1 ;
				int x = ( ans[i] - 1 ) / 9 / 9 + 1 ;
				int y = ( ans[i] - 1 ) / 9 % 9 + 1 ;
				G[x][y] = Orz ;
			}
			FOR ( i , 1 , 9 ) {
				FOR ( j , 1 , 9 )
					printf ( "%d" , G[i][j] ) ;
				printf ( "\n" ) ;
			}
		}
	}
} dlx ;

int main () {
	int T ;
	scanf ( "%d" , &T ) ;
	while ( T -- ) {
		dlx.solve () ;
		if ( T )
			printf ( "\n" ) ;
	}
	return 0 ;
}