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