A - GREAT+SWERC=PORTO Gym - 100783A 简单dfs

本文主要是介绍A - GREAT+SWERC=PORTO Gym - 100783A 简单dfs，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：

给出一个算式，算式中的数字用大写字母代替

每个字母只能代替一个数字，一个数字也只能被一个字母代替

问：有多少种数字分配方式可以使得这个算式成立

题解：

dfs

一共不超过十个字母，把这十个字母列出来然后进行dfs分配数字

分配完后就进行验证是否可以满足式子

注意每一行对应的数开头不能是0

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;int len[20],n,p;
char str[20][20];
int used[30],visit[30];
struct letter
{char ch;int num,flag;
}a[20];
#define LL long longint check()
{int t,sum=0,num=0;for(int i=1;i<n;i++){t=0;for(int j=0;j<len[i];j++)t=t*10+visit[str[i][j]-'A'];sum+=t;}for(int i=0;i<len[n];i++)num=num*10+visit[str[n][i]-'A'];if(sum==num)return 1;return 0;
}LL dfs(int pos)
{LL ans=0;if(pos>=p)return check()?1:0;for(int i=0;i<=9;i++){if(used[i]==0){if(a[pos].flag==0&&i==0)continue;a[pos].num=i;visit[a[pos].ch-'A']=i;used[i]=1;ans+=dfs(pos+1);used[i]=0;}}return ans;
}int main()
{//freopen("in.txt","r",stdin);while(scanf("%d",&n)!=EOF){p=0;memset(visit,0,sizeof(visit));for(int i=1;i<=n;i++){scanf("%s",str[i]);len[i]=strlen(str[i]);for(int j=0;j<len[i];j++){if(!visit[str[i][j]-'A']){a[p].flag=1;a[p++].ch=str[i][j],visit[str[i][j]-'A']=1;}if(j==0){for(int k=0;k<p;k++)if(a[k].ch==str[i][j])a[k].flag=0;}}}LL ans=0;memset(used,0,sizeof(used));ans=dfs(0);printf("%lld\n",ans);}return 0;
}

这篇关于A - GREAT+SWERC=PORTO Gym - 100783A 简单dfs的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---