题目链接

P1092 虫食算

解题思路

好题啊！这个搜索好难写......

大概是要考虑进位和考虑使用过某个数字这两个东西，但就很容易出错......

首先这个从后往前搜比较好想，按照从后往前出现的顺序搜，在这个剪枝条件下速度会快很多。

比如样例，

5

ABCED

BDACE

EBBAA

从右往左出现的次序是\(DEAECACABBDBABE\)，去重之后是\(DEACB\)，这就是要搜索的顺序，用\(seq\)记录。

当某时候等式明显已经不满足时，就直接\(return\)。

还有别的剪枝，但这样直接能\(79ms\)。没必要。

AC代码

#include<stdio.h>

#include<stdlib.h>

#define N 30

int n,a[N],b[N],c[N],vis[N],ans[N];

char s[3][N];

int seq[N];//搜索顺序

void dfs(int x){//搜到第x个元素

	int i,jw=0;

	if(ans[a[0]]+ans[b[0]]>=n)return;

	for(i=n-1;i>=0;i--){//从后往前检查

		int A=ans[a[i]],B=ans[b[i]],C=ans[c[i]];

		if(A==-1||B==-1||C==-1)continue;

		if((A+B+1)%n!=C&&(A+B)%n!=C)return;

	}

	if(x==n){

		for(i=n-1;i>=0;i--){

			int A=ans[a[i]],B=ans[b[i]],C=ans[c[i]];

			if((A+B+jw)%n!=C)return;

			jw=(A+B+jw)/n;

		}

		for(i=0;i<n;i++)printf("%d ",ans[i]);

		exit(0);

	}

	for(i=n-1;i>=0;i--){

		if(!vis[i]){

			vis[i]=1;ans[seq[x]]=i;

			dfs(x+1);

			vis[i]=0;ans[seq[x]]=-1;

		}

	}

}

int cnt;

void f(int x){//提供搜索顺序，加快搜索速度

	if(!vis[x]){vis[x]=1;seq[cnt++]=x;}

}

int main(){

	int i;

	for(i=0;i<30;i++)ans[i]=-1;

	scanf("%d%s%s%s",&n,s[0],s[1],s[2]);

	for(i=0;i<n;i++){

		a[i]=s[0][i]-'A';

		b[i]=s[1][i]-'A';

		c[i]=s[2][i]-'A';

	}

	for(i=n-1;i>=0;i--){f(a[i]);f(b[i]);f(c[i]);}

	for(i=0;i<n;i++)vis[i]=0;

	dfs(0);

	return 0;

}

这是seq优化后的结果：

这是从n-1到1搜索的结果：

而这是从1到n-1搜索的结果：