PKU-3600 Subimage Recognition

問題概要

0と1からなる二つの画像A,Bが与えられる．
Bの任意の行と列を消して画像Aが作り出せるかを求めよ．

解法

行の消し方を全部調べると，列の消し方は貪欲に求めることが出来る．
行の消し方は20C10なので20C10*20*20で十分間に合う．

実装

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <bitset>
#include <set>
using namespace std;
int r,c;
int MAP[20][20];
int R,C;
int image[20][20];
#define REP(i,x)for(int i=0;i<(int)x;i++)
int ans=0;
bool used_row[20];
bool comp_col(int x,int y){
	int cnt=0;
	REP(i,R){
		if(used_row[i]==false)continue;
		if(MAP[cnt][x]!=image[i][y])return false;
		cnt++;
	}
	return true;
}
bool solve(){
	int now=0;
	REP(i,C){
		if(now>=c)break;
		if(comp_col(now,i))now++;
	}
	if(now==c)return true;
	return false;
}
void dfs(int x,int count){
	if(count>r)return;
	if(x==R){
		if(count==r){
			/*
			cout<<"!"<<endl;
			REP(i,R){
				cout<<used_row[i];
			}
			cout<<endl;*/
			if(solve()){

				ans=true;
			}
		}
		return;
	}
	used_row[x]=1;
	dfs(x+1,count+1);
	if(ans)return;
	used_row[x]=0;
	dfs(x+1,count);
	if(ans)return;

}

int main() {
	cin>>r>>c;
	REP(i,r){
		string in;
		cin>>in;
		REP(j,c){
			MAP[i][j]=(in[j]=='1');
		}
	}
	cin>>R>>C;
	REP(i,R){
		string in;
		cin>>in;
		REP(j,C){
			image[i][j]=(in[j]=='1');
		}
	}
	dfs(0,0);
	if(ans){
		cout<<"Yes"<<endl;
	}else{
		cout<<"No"<<endl;
	}
	return 0;
}