萌新求助DFS90分
查看原帖
萌新求助DFS90分
308854
tzl_Dedicatus545楼主2020/6/6 12:05

RTRT,代码:

#include <iostream>
#include <cctype>
#include <cstring>
#include <cstdlib>

using namespace std;

string a[3];
//int ans[5][27]={0};
bool visit[27];
char next000[27];
bool hash2[100];
int h[27];

inline bool judge(int n)
{	
	int jin=0;
	
	for(register int i=n-1;i>=0;i--)
	{
		if((h[a[0][i]-'A']+h[a[1][i]-'A']+jin)%n==h[a[2][i]-'A'])
		{
			jin=(h[a[0][i]-'A']+h[a[1][i]-'A']+jin)/n;
		}
		else
			return false;
	}
	
	if(jin==1)
		return false;
		
	return true;
}

inline bool jianzhi(int n)
{
	if(h[a[0][0]-'A']+h[a[1][0]-'A']>=n)
		return false;

	for(register int i=0;i<n;i++)
	{
		if(h[a[0][i]-'A']!=-1 && h[a[1][i]-'A']!=-1 && h[a[2][i]-'A']!=-1)
		{
			if((h[a[0][i]-'A']+h[a[1][i]-'A'])%n!=h[a[2][i]-'A'] && (h[a[0][i]-'A']+h[a[1][i]-'A']+1)%n!=h[a[2][i]-'A'])
				return false;
		}
	}
	
	return true;
}

inline void tian(char t,int kk)
{
	h[t-'A']=kk;
}

void dfs(int t,int n)
{
	if(!jianzhi(n))
		return ;
	if(t==n && judge(n))	
	{
		for(register int i=0;i<n;i++)
			cout<<h[i]<<" ";
		exit(0);
	}
	
	for(register int i=0;i<n;i++)
	{
		if(!visit[i])
		{
			//cout<<i<<' ';
			visit[i]=1;
			tian(next000[t],i);
			//print(n);
			dfs(t+1,n);
			visit[i]=0;
			tian(next000[t],-1);
		}
	}
}

inline void getnext(int n)
{
	//bool hash2[n];

	register int cnt=0;
	for(register int i=0;i<n;i++)
	{
		for(register int j=0;j<3;j++)
		{
			if(!hash2[a[j][i]-'A'])
			{
				hash2[a[j][i]-'A']=1;
				next000[cnt++]=a[j][i];
			}
		}
	}
}

int main()
{
	ios::sync_with_stdio(0);
	int n;
	
	//cout<<judge(5);
	cin>>n;
	
	memset(h,-1,sizeof(h));
	
	cin>>a[0]>>a[1]>>a[2];
	
	getnext(n);
	
	dfs(0,n);
	

	return 0;
}

2020/6/6 12:05
加载中...