Problem 1022 : Indian Puzzle

問題概要

日本語なので詳しくは本文参照。
（http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1022）

盤面
4=..2
+#=#+
.-2=.
=#*#=
.-.=3

空白を埋める候補
7 3 1 4 / 8

のようなパズルの盤面および候補が与えられる。
'#'は壁で、そこで等式が途切れる。
'.'は空白で、そこに候補の数字or演算子を入れる。

全ての等式（長さ3以上の文字列。これらは=がただ一つ含まれることが保証されている）が成り立つように候補の数字を埋めることができるかどうかを判定せよ。

解法

深さ優先探索+構文解析
式がなるべく早く出来るように適当な順に'.'に優先順位をつけ、
その順に候補を入れていった。

式が正しく成り立っているかは構文解析により式を評価してみればよい。

int h,w,n;
char bd[10][11];
char lst[10];
int dx[10],dy[10];

int eval(char *expr,int s,int t)
{
	if(s>=t)return inf;
	
	int p=t-1;
	for(;p>=s;p--)if(expr[p]=='+'||expr[p]=='-')break;
	if(p>=s)
	{
		int a=eval(expr,s,p),b=eval(expr,p+1,t);
		if(a==inf||b==inf)return inf;
		return expr[p]=='+'?a+b:a-b;
	}
	
	for(p=t-1;p>=s;p--)if(expr[p]=='*'||expr[p]=='/')break;
	if(p>=s)
	{
		int a=eval(expr,s,p),b=eval(expr,p+1,t);
		if(a==inf||b==inf)return inf;
		if(expr[p]=='/'&&(b==0||a%b!=0))return inf;
		return expr[p]=='*'?a*b:a/b;
	}
	
	if(t>s+1&&expr[s]=='0')return inf;
	
	int ret=0;
	for(p=s;p<t;p++)ret*=10,ret+=expr[p]-'0';
	return ret;
}
bool ok(char *expr,int l)
{
	int eq=-1;
	rep(i,l)if(expr[i]=='=')eq=eq==-1?i:-2;
	
	assert(eq>=0); assert(l>0);
	rep(i,l)assert(expr[i]!='.');
	
	int a=eval(expr,0,eq),b=eval(expr,eq+1,l);
	return a!=inf&&b!=inf&&a==b;
}
bool valid(int y,int x)
{
	if(y<0||y>=h||x<0||x>=w)return 0;
	return bd[y][x]!='#';
}

//あるマスについて、そこから横と縦に伸びる数式が正しいかをチェックする関数
int ck(int y,int x)//-1:矛盾 0:未確定 1:無矛盾
{
	int sy,ty,sx,tx;
	for(sy=y-1;valid(sy,x);sy--); for(ty=y+1;valid(ty,x);ty++);
	for(sx=x-1;valid(y,sx);sx--); for(tx=x+1;valid(y,tx);tx++);
	sy++; sx++;
	
	char tate[11]={0},yoko[11]={0}; int t=0,yo=0;
	bool teq=0,yeq=0,tdot=0,ydot=0;
	for(int i=sy;i<ty;i++)
	{
		tate[t++]=bd[i][x];
		if(bd[i][x]=='=')teq=1;
		else if(bd[i][x]=='.')tdot=1;
	}
	for(int i=sx;i<tx;i++)
	{
		yoko[yo++]=bd[y][i];
		if(bd[y][i]=='=')yeq=1;
		else if(bd[y][i]=='.')ydot=1;
	}
	
	int tok,yok;
	if(t>1&&!teq||yo>1&&!yeq)return -1;
	if(tdot)tok=0; else tok=t<3||ok(tate,t)?1:-1;
	if(ydot)yok=0; else yok=yo<3||ok(yoko,yo)?1:-1;
	
	return tok<0||yok<0?-1:tok>0&&yok>0?1:0;
}
bool rec(int c)
{
	if(c==n)
	{
		rep(i,h)rep(j,w)if(bd[i][j]=='='&&ck(i,j)<=0)return 0;
		return 1;
	}
	
	rep(i,n)if(lst[i])
	{
		bd[dy[c]][dx[c]]=lst[i]; lst[i]=0;
		if(ck(dy[c],dx[c])>=0&&rec(c+1))return 1;
		lst[i]=bd[dy[c]][dx[c]]; bd[dy[c]][dx[c]]='.';
	}
	return 0;
}

int main()
{
	while(scanf("%d%d",&h,&w),h)
	{
		rep(i,h)scanf("%s",bd[i]);
		scanf("%d",&n);
		rep(i,n)scanf(" %c",lst+i);
		
		int c=0;
		bool use[10][10]={0};
		
		rep(i,h)rep(j,w)if(bd[i][j]=='=')//適当に優先順位をつける
		{
			for(int k=j+1;valid(i,k);k++)if(bd[i][k]=='.'&&!use[i][k])
			use[i][k]=1,dy[c]=i,dx[c]=k,c++;
			
			for(int k=j-1;valid(i,k);k--)if(bd[i][k]=='.'&&!use[i][k])
			use[i][k]=1,dy[c]=i,dx[c]=k,c++;
			
			for(int k=i+1;valid(k,j);k++)if(bd[k][j]=='.'&&!use[k][j])
			use[k][j]=1,dy[c]=k,dx[c]=j,c++;
			
			for(int k=i-1;valid(k,j);k--)if(bd[k][j]=='.'&&!use[k][j])
			use[k][j]=1,dy[c]=k,dx[c]=j,c++;
		}
		
		puts(rec(0)?"Yes":"No");
	}
	return 0;
}