POJ 3600 Subimage Recognition

問題

r行c列の'0','1'の行列AとR行C列の'0','1'の行列Bが与えられる。
Bの一部の行と、一部の列を削って、Aを作ることはできるか答えよ。

制約条件

r≦R≦20
c≦C≦20

方針

枝刈り+深さ優先探索

Bのi列に対して、Aのj列を部分文字列として含むかをok[i][j]として計算しておく。
列についてdfsして、Bの列の選び方を全て試す。
その際にok[i][j]により枝刈りする。

列を全て選び終わったら、そこから行をgreedyに選び、Aが作れるかを試す。

実は枝刈りなしでも通る。

ソースコード

int r,c,R,C;
char A[20][20], B[20][20];
bool ok[20][20];
int anum[20],tmp[20];

bool dfs(int cur,int use){
	if(use==c){
		int i=0, j=0;
		for(;i<R&&j<r; i++){
			while(i<R&&tmp[i]!=anum[j])i++;
			if(i<R)j++;
		}
		return j==r;
	}
	if(cur==C)return 0;
	if(ok[cur][use]){
		rep(i,R)if(B[i][cur]=='1')tmp[i]|=1<<use;
		if(dfs(cur+1,use+1))return 1;
		rep(i,R)if(B[i][cur]=='1')tmp[i]^=1<<use;
	}
	return dfs(cur+1,use);
}

int main()
{
	scanf("%d%d",&r,&c);
	rep(i,r){
		scanf("%s",A[i]);
		rep(j,c)if(A[i][j]=='1')anum[i]|=1<<j;
	}
	scanf("%d%d",&R,&C);
	rep(i,R)scanf("%s",B[i]);
	
	rep(i,C)rep(j,c){
		int k=0, l=0;
		for(;k<R&&l<r; k++){
			while(k<R&&B[k][i]!=A[l][j])k++;
			if(k<R)l++;
		}
		if(l>=r)ok[i][j]=1;
	}
	
	puts(dfs(0,0)?"Yes":"No");
	
	return 0;
}