题目描述
所谓虫食算,就是原先的算式中有一部分被虫子啃掉了,需要我们根据剩下的数字来判定被啃掉的字母。
来看一个简单的例子:
43#9865#045
+ 8468#6633
--------------
44445506978
其中#号代表被虫子啃掉的数字。
根据算式,我们很容易判断:第一行的两个数字分别是5和3,第二行的数字是5。
现在,我们对问题做两个限制:
首先,我们只考虑加法的虫食算。这里的加法是N进制加法,算式中三个数都有N位,允许有前导的0。
其次,虫子把所有的数都啃光了,我们只知道哪些数字是相同的,我们将相同的数字用相同的字母表示,不同的数字用不同的字母表示。
如果这个算式是N进制的,我们就取英文字母表的前N个大写字母来表示这个算式中的0到N-1这N个不同的数字:但是这N个字母并不一定顺序地代表0到N-1。
输入数据保证N个字母分别至少出现一次。
BADC
+ CBDA
----------
DCCC
上面的算式是一个4进制的算式。
很显然,我们只要让ABCD分别代表0123,便可以让这个式子成立了。
你的任务是,对于给定的N进制加法算式,求出N个不同的字母分别代表的数字,使得该加法算式成立。
输入数据保证有且仅有一组解。
样例
输入样例:
5
ABCED
BDACE
EBBAA
输出样例:
1 0 3 4 2
算法1
(搜索 + 剪枝)
dfs 顺序:从低位往高位算,因为有进位,因此可以判断进位后运算是否发生错误,来剪枝。
需要用q[depth]
数组,来存储哪些数标记过,哪些数没标记过, 方便后续dfs。
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <cstring>
using namespace std;
const int N = 30;
int n;
char e[3][N];
int q[N], path[N];//q表示队列,从低位到高位记录需要枚举的数。
bool st[N];
bool check(){
for (int i = n - 1, t = 0; i >= 0; i -- ){
int a = e[0][i] - 'A', b = e[1][i] - 'A', c = e[2][i] - 'A';
if (path[a] != -1 && path[b] != -1 && path[c] != -1){ //如果a, b, c都作过映射
a = path[a], b = path[b], c = path[c];
if (t != -1){ //t表示进位
if ((a + b + t) % n != c) return false;
if (!i && a + b + t >= n) return false;
t = (a + b + t) / n;
}else {
if ( (a + b + 0) % n != c && (a + b + 1) % n != c) return false;
if (!i && a + b >= n) return false; //当前位数为n的情况下,搜索出来最高位存在进位,那么必定出错了
}
}else t = -1;//如果a, b, c中其中有一个没作过映射, 那么进位只可能是0, 1. 会上下一次check的时候进入上面else分支
}
return true;
}
bool dfs(int u){
if (u == n) return true;
for (int i = 0; i < n; i ++ ){//从0(即样例中的'A')开始枚举,0 应该变成数字几
if (!st[i]){//如果'0'没有作过映射
st[i] = true;
path[q[u]] = i;
if (check() && dfs(u + 1)) return true;
st[i] = false;
path[q[u]] = -1;
}
}
return false;
}
int main(){
scanf("%d", &n);
for (int i = 0; i < 3; i ++ ) scanf("%s", &e[i]);
for (int i = n - 1, k = 0; i >= 0; i -- )//从低位开始预处理,扣出已经填好的数字.
for (int j = 0; j < 3; j ++ ){ //j表示行数,遍历0到2行
int t = e[j][i] - 'A';//将所在位置的字符并转化为数字,方便处理
if (!st[t]){
st[t] = true;//标记为已填过
q[k ++ ] = t; //用数组记录填过的数字, dfs中方便查找.
}
}
memset(st, 0, sizeof st);
memset(path, -1, sizeof path);
dfs(0);
for (int i = 0; i < n; i ++ ) printf("%d ", path[i]);
return 0;
}