chtholly-daisuki的小屋

「器用贫乏」

0%

abc326-d 题解

发表于 更新于 分类于 ， ，
比较麻烦的暴力搜索

题目链接一开始读错题了，以为abc可以出现多次，浪费了很多时间，一定要戒骄戒躁读好题！这种搜索题要思路打开，想一想以什么搜索按列去搜索，感觉自己写的有点麻烦了我的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<bits/stdc++.h>
using namespace std;
int n;
string rr,cc;//row,column
int r[10],c[10];
int cntr[10];//row [i] is empty是否前面没有字母：需要向r对齐
bool ise[10][10];//ise[i][j]: 字母j是否存在于rowi中 
int mp[10][10];
bool flag=false;
int ans=0;
void out(){
	cout<<"Yes"<<endl;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(mp[i][j]==-1) cout<<".";
			else cout<<(char)(mp[i][j]+'A');
		}
		cout<<endl;
	}
	/*for(int i=1;i<=n;i++){
		for(int j=0;j<=2;j++){
			cout<<ise[i][j];
		}
		cout<<endl;
	}
	cout<<"-------------------";*/
}
void dfs(int iofc){//i of column: dfs每一个column c35 * 2的样本空间 
	if(flag) return;
	if(iofc==n+1){
		flag=1;
		out();
	}
	//cout<<endl;
	//cout<<iofc<<endl;
	//out();
	for(int i=1;i<=n-2;i++){//每个column的第一个数
		int x=c[iofc],y=(c[iofc]+1)%3,z=(c[iofc]+2)%3;
		if(ise[i][x]) continue;//
		if(cntr[i]==0&&x!=r[i]) continue;
		ise[i][c[iofc]]=1; mp[i][iofc]=c[iofc]; cntr[i]++;
		//c[i]+1为此列的第二个数 
		for(int j=i+1;j<=n-1;j++){
			if(ise[j][y]) continue;//改1 
			if(cntr[j]==0&&y!=r[j]) continue;
			ise[j][y]=1; mp[j][iofc]=y; cntr[j]++;
			for(int k=j+1;k<=n;k++){
				if(ise[k][z]) continue;
				if(cntr[k]==0&&z!=r[k]) continue;
				ise[k][z]=1; mp[k][iofc]=z; cntr[k]++;
				dfs(iofc+1);
				ise[k][z]=0; mp[k][iofc]=-1; cntr[k]--;
			}
			ise[j][y]=0; mp[j][iofc]=-1; cntr[j]--;
		}
		//c[i]+1为此列的第三个数 
		z=(c[iofc]+1)%3;y=(c[iofc]+2)%3;
		for(int j=i+1;j<=n-1;j++){
			if(ise[j][y]) continue;
			if(cntr[j]==0&&y!=r[j]) continue;
			ise[j][y]=1; mp[j][iofc]=y; cntr[j]++;//注意取余 
			for(int k=j+1;k<=n;k++){
				if(ise[k][z]) continue;
				if(cntr[k]==0&&z!=r[k]) continue;
				ise[k][z]=1; mp[k][iofc]=z; cntr[k]++;
				dfs(iofc+1);
				ise[k][z]=0; mp[k][iofc]=-1; cntr[k]--;
			}
			ise[j][y]=0; mp[j][iofc]=-1; cntr[j]--;
		}
		ise[i][x]=0; mp[i][iofc]=-1; cntr[i]--;
	}
	
}

int main(){
	ios::sync_with_stdio(0);
	cout.tie(0);
	cin>>n;
	cin>>rr>>cc;
	for(int i=1;i<=n;i++) r[i]=rr[i-1]-'A';
	for(int i=1;i<=n;i++) c[i]=cc[i-1]-'A';
	memset(mp,-1,sizeof(mp));
	memset(cntr,0,sizeof(cntr));
	dfs(1);
	if(!flag) cout<<"No";
	return 0;
}