萌新求助DFS90分
查看原帖
萌新求助DFS90分
658786
STUDENT00楼主2022/10/7 15:42

代码如下:

#include<bits/stdc++.h>
#define to(a) (a-'A')
using namespace std;
int n,s[26],ans[26],k;
char a[26],b[26],c[26];
bool use[26],vis[26];
void make(char c){
	if(!use[to(c)]){
		use[to(c)]=1;
		s[k++]=to(c);
	}
	return;
}
bool cb(){
	for(int i=0;i<n;i++){
		int t1=ans[to(a[i])],t2=ans[to(b[i])],t3=ans[to(c[i])];
		if(t1==-1||t2==-1||t3==-1) continue;
		if((t1+t2)%n!=t3&&(t1+t2+1)%n!=t3) return 1;
	}
	return 0;
}
bool check(){
	int x=0;
	for(int i=n-1;i>=0;i--){
		int s=ans[to(a[i])]+ans[to(b[i])]+x;
		if(s%n!=ans[to(c[i])]) return 0;
		x=s/n;
	}
	if(x>0) return 0;
	return 1;
}
void dfs(int now){
	if(cb()) return;
	if(now==n){
		if(check()){
			for(int i=0;i<n;i++) printf("%d ",ans[i]);
			exit(0);
		}
		return;
	}
	for(int i=0;i<n;i++){
		if(!vis[i]){
			ans[s[now]]=i;
			vis[i]=1;
			dfs(now+1);
			vis[i]=0;
			ans[s[now]]=-1;
		}
	}
	return;
}
int main(){
	scanf("%d%s%s%s",&n,a,b,c);
	for(int i=0;i<n;i++){
		make(a[i]);
		make(b[i]);
		make(c[i]);
	}
	memset(ans,-1,sizeof(ans));
	dfs(0);
	return 0;
}
2022/10/7 15:42
加载中...