SRM 315 Div1 Medium SillySudoku

問題概要

4x4のミニサイズの数独がある。

ある時点での盤面があたえられた時、この数独を完成パターンは何通りあるかを求めよ。
パズルで用いる数字は1-4であり、その他のルールは通常の数独と同じである。また数字がないマスは'-'で表される。

この回早解き勝負だったのかな。

解法

実行時間は気にしなくて良いよく、単純に再帰で数え上げればよい。
現在の盤面が合法かどうかをいちいち全て見て調べる（下コードではok関数）という効率の悪いやり方でも制限時間に間に合う。

ソースコード

	map<vs,int> memo;
	int countWays(vector <string> board) 
	{
		return rec(board);
	}
	int rec(vs b)
	{
		if(memo.count(b))return memo[b];
		if(!ok(b))return memo[b]=0;
		
		bool f=0;
		int ret=0;
		rep(i,4)rep(j,4)if(b[i][j]=='-')
		{
			f=1;
			rep(n,4)
			{
				b[i][j]='1'+n;
				ret+=rec(b);
				b[i][j]='-';
			}
			goto END;
		}
		END:return f?(memo[b]=ret):1;
	}
	bool ok(vs b)
	{
		//col
		rep(j,4)
		{
			bool u[4]={0};
			rep(i,4)
			{
				if(b[i][j]=='-')continue;
				if(u[b[i][j]-'1'])return 0;
				u[b[i][j]-'1']=1;
			}
		}
		//row
		rep(i,4)
		{
			bool u[4]={0};
			rep(j,4)
			{
				if(b[i][j]=='-')continue;
				if(u[b[i][j]-'1'])return 0;
				u[b[i][j]-'1']=1;
			}
		}
		//box
		rep(y,2)rep(x,2)
		{
			bool u[4]={0};
			rep(i,2)rep(j,2)
			{
				if(b[y*2+i][x*2+j]=='-')continue;
				if(u[b[y*2+i][x*2+j]-'1'])return 0;
				u[b[y*2+i][x*2+j]-'1']=1;
			}
		}
		return 1;
	}

メモ化は別に要らなかったみたい……

System Test

Passed.
でも解くの遅い。。。orz