TIOJ 1581 KUKUKU Game [DFS]

poao899    -8K    150MS    G++     1.75K     2009-11-18 20:36:55                         .

總算不是排序了(咦

這題比TIOJ 1025 數獨問題 ( 96校內賽 prob 2 ) 還陰多了QQ

會有一開始不合法、甚至0~4以外的數字出現

雖然如果吃過RE不難想到xD

//*****************************

#include<stdio.h>
int sudo[4][4];
int cnt;
void dfs(int i,int j){
	//printf("%d %d\n",i,j);
	if(i==4){
		cnt++;
		if(cnt!=1)return;
		for(int k=0;k<4;k++){
			for(int l=0;l<4;l++)
				putchar(sudo[k][l]+48);
			puts("");
		}
		puts("");
		return;
	}
	bool find=0;
	for(;i<4;i++){
		for(;j<4;j++){
			//printf("%d %d:%d\n",i,j,sudo[i][j]);
			if(sudo[i][j]==0){
				find=1;
				break;
			}
		}
		if(find)break;
		j=0;
	}
	if(i==4){
		dfs(i,j);
		return;
	}
	bool used[5]={};
	for(int k=0;k<4;k++){
		used[sudo[k][j]]=1;
		used[sudo[i][k]]=1;
	}
	for(int k=0;k<2;k++)
		for(int l=0;l<2;l++)
			used[sudo[k+i/2*2][l+j/2*2]]=1;
	for(int k=1;k<5;k++){
		//printf("%d %d:%d\n",i,j,k);
		if(!used[k]){
			//printf("%d %d:%d\n",i,j,k);
			sudo[i][j]=k;
			dfs(i,j);
		}
	}
	sudo[i][j]=0;
}
main(){
	for(int i=0;i<4;i++)
		for(int j=0;j<4;j++){
			scanf("%d",&sudo[i][j]);
			if(sudo[i][j]>4||sudo[i][j]<0){
				puts("I can not solve!!");
				return 0;
			}
		}
	bool used[5]={};
	for(int i=0;i<4;i++){
		for(int j=0;j<5;j++)used[j]=0;
		for(int j=0;j<4;j++){
			int c=sudo[i][j];
			if(c&&used[c]){
				puts("I can not solve!!");
				return 0;
			}
			used[c]=1;
		}
		for(int j=0;j<5;j++)used[j]=0;
		for(int j=0;j<4;j++){
			int c=sudo[j][i];
			if(c&&used[c]){
				puts("I can not solve!!");
				return 0;
			}
			used[c]=1;
		}
	}
	for(int i=0;i<3;i+=2)
		for(int j=0;j<3;j+=2){
			for(int k=0;k<5;k++)used[k]=0;
			for(int k=0;k<2;k++)
				for(int l=0;l<2;l++){
					int c=sudo[i+k][j+l];
					if(c&&used[c]){
						puts("I can not solve!!");
						return 0;
					}
					used[c]=1;
				}
		}
	dfs(0,0);
	if(cnt)printf("We have %d way(s) to solve it!!\n",cnt);
	else puts("I can not solve!!");
}