PKU演習問メモ(9/17)

もういやもういやもういやもういやもういやもういやもういや

No.	問題名	問題の種類および解法	難易度
2918	Tudoku	実装	★★☆☆☆

2918 Tudoku

問題概要

Sudokuの簡単なバージョン（盤面を全て一意に決めていくことができるので探索の必要がない）

解法

ソースコード

int row[9],col[9],box[9];
char in[9][10];

int main()
{
	int CS; scanf("%d",&CS);
	rep(cs,CS)
	{
		rep(i,9)scanf("%s",&in[i]);
		rep(i,9)row[i]=col[i]=box[i]=0;
		
		int cnt=0;
		rep(i,9)rep(j,9)if(in[i][j]!='0')
		{
			cnt++;
			int t=1<<in[i][j]-'1';
			row[i]|=t; col[j]|=t; box[i/3*3+j/3]|=t;
		}
		while(cnt<81)
		{
			rep(i,9)rep(j,9)if(in[i][j]=='0')
			{
				int t=(1<<9)-1;
				t&=~row[i]&~col[j]&~box[i/3*3+j/3];
				
				int u=-1;
				rep(k,9)if(t&1<<k)
				{
					if(u==-1)u=k;
					else u=-2;
				}
				if(u<0)continue;
				cnt++; in[i][j]='1'+u;
				row[i]|=1<<u; col[j]|=1<<u; box[i/3*3+j/3]|=1<<u;
			}
		}
		printf("Scenario #%d:\n",cs+1);
		rep(i,9)puts(in[i]); puts("");
	}
	return 0;
}