三羊献瑞 DFS 枚举
三羊献瑞
题目描述
观察下面的加法算式：
祥 瑞 生 辉 + 三 羊 献 瑞 ------------------- 三 羊 生 瑞 气其中，相同的汉字代表相同的数字，不同的汉字代表不同的数字。
请你输出“三羊献瑞”所代表的 4 位数字（答案唯一）。
运行限制
- 最大运行时间：1s
- 最大运行内存: 128M
题目分析
我们可以通过DFS 枚举每一个字母对应的数字（0~9）
并且由于：
- 已使用数字不能重复
- 首位数字不能为 0（a、e）
来进行剪枝
代码如下：
#include<bits/stdc++.h>usingnamespacestd;inta[8];// 8个字母boolused[10];voiddfs(intpos){if(pos==8){intx=a[0]*1000+a[1]*100+a[2]*10+a[3];inty=a[4]*1000+a[5]*100+a[6]*10+a[1];intz=a[4]*10000+a[5]*1000+a[2]*100+a[1]*10+a[7];if(x+y==z){cout<<a[4]*1000+a[5]*100+a[6]*10+a[1]<<endl;exit(0);}return;}for(inti=0;i<=9;i++){if(used[i])continue;// 首位不能为0if((pos==0||pos==4)&&i==0)continue;used[i]=true;a[pos]=i;dfs(pos+1);used[i]=false;}}intmain(){dfs(0);return0;}