Codeforces 71 D. Solitaire

問題

トランプ54枚のうちnm枚がn行m列に並んでいる。

ジョーカーを余っているカードの好きなものと取り替えてよい。
このとき、次のうちいずれかの条件を満たす3x3の正方形を重ならないように二つ取ることが出来るか判定せよ。

• 全てのスートが同じ
• 全ての数字が互いに異なる

制約条件

n,m≦17
nm≦52

方針

全探索。

ソースコード

これは酷い。

int h,w;
int cd[20][20];
bool use[200];
int parse(string s){
	int res=0;
	if(isdigit(s[1]))return -(s[1]-'0');
	switch(s[0]){
	case 'A': res=1; break;
	case 'T': res=10; break;
	case 'J': res=11; break;
	case 'Q': res=12; break;
	case 'K': res=13; break;
	default: res=s[0]-'0';
	}
	res*=5;
	switch(s[1]){
	case 'S':; break;
	case 'H': res+=1; break;
	case 'D': res+=2; break;
	case 'C': res+=3; break;
	}
	return res;
}
const char *name="SHDC";
const char *ranks="-A23456789TJQK";
string ans1,ans2;
bool ok(int y,int x){
	bool samesuit=1;
	bool use[14]={};
	rep(i,3)rep(j,3){
		if(cd[i+y][j+x]%5!=cd[y][x]%5)samesuit=0;
		use[cd[i+y][j+x]/5]=1;
	}
	int cnt=0;
	rep(i,14)if(use[i])cnt++;
	return samesuit||cnt==9;
}
bool ck(){
	rep(i,h-2)rep(j,w-2){
		if(!ok(i,j))continue;
		rep(k,h-2)rep(l,w-2)if(abs(i-k)>=3||abs(j-l)>=3){
			if(!ok(k,l))continue;
			stringstream ss;
			ss<<"Put the first square to ("<<i+1<<", "<<j+1<<").";
			ans1=ss.str();
			stringstream tt;
			tt<<"Put the second square to ("<<k+1<<", "<<l+1<<").";
			ans2=tt.str();
			return 1;
		}
	}
	return 0;
}
void run()
{
	cin>>h>>w;
	int j1y=-1,j1x=-1,j2y=-1,j2x=-1;
	rep(i,h)rep(j,w){
		string s; cin>>s;
		cd[i][j]=parse(s);
		if(cd[i][j]==-1)j1y=i, j1x=j;
		else if(cd[i][j]==-2)j2y=i, j2x=j;
		use[cd[i][j]]=1;
	}
	if(j1y<0&&j2y<0){
		if(ck()){
			cout<<"Solution exists."<<endl;
			cout<<"There are no jokers."<<endl;
			cout<<ans1<<endl<<ans2<<endl;
			return;
		}
		cout<<"No solution."<<endl;
		return;
	}
	if(j1y>=0&&j2y<0){
		rep(suit1,4)for(int rank1=1;rank1<=13;rank1++){
			if(!use[suit1+rank1*5]){
				cd[j1y][j1x]=suit1+rank1*5;
				if(ck()){
					cout<<"Solution exists."<<endl;
					cout<<"Replace J1 with "<<ranks[rank1]<<name[suit1]<<"."<<endl;
					cout<<ans1<<endl<<ans2<<endl;
					return;
				}
			}
		}
		cout<<"No solution."<<endl;
		return;
	}
	if(j1y<0&&j2y>=0){
		rep(suit1,4)for(int rank1=1;rank1<=13;rank1++){
			if(!use[suit1+rank1*5]){
				cd[j2y][j2x]=suit1+rank1*5;
				if(ck()){
					cout<<"Solution exists."<<endl;
					cout<<"Replace J2 with "<<ranks[rank1]<<name[suit1]<<"."<<endl;
					cout<<ans1<<endl<<ans2<<endl;
					return;
				}
			}
		}
		cout<<"No solution."<<endl;
		return;
	}
	rep(suit1,4)for(int rank1=1;rank1<=13;rank1++)if(!use[suit1+rank1*5]){
		rep(suit2,4)for(int rank2=1;rank2<=13;rank2++)
		if((suit1!=suit2||rank1!=rank2)&&!use[suit2+rank2*5]){
			cd[j1y][j1x]=suit1+rank1*5;
			cd[j2y][j2x]=suit2+rank2*5;
			if(ck()){
				cout<<"Solution exists."<<endl;
				cout<<"Replace J1 with "<<ranks[rank1]<<name[suit1];
				cout<<" and J2 with "<<ranks[rank2]<<name[suit2]<<"."<<endl;
				cout<<ans1<<endl<<ans2<<endl;
				return;
			}
		}
	}
	cout<<"No solution."<<endl;
}