UVA_185
第一部分就不详细说了，把字符串翻译成整数即可，关键在于第二部分，这个就像小的时候玩的填数字的数学题。
首先，我们不妨分析一下题目的特征，并试图找尽量多的回溯的条件。
显然我们应该从个位加和算起，这样既符合我们的运算习惯，也方便我们对表达式求值。我们不妨设对竖式的每一列的分析都是x+y+s=z的形式，其中s为前一位进上来的余数，那么我们当然选择去枚举x和y的值，这样z就自然确定了，如果枚举z的值话就显得麻烦多了。
在枚举x和y的时候都会遇到三种情况，第一种情况是这个字符在前面的运算中已被赋了一个值了，第二种情况是这个字符还没有被赋过值，第三种情况就是不存在这一位（说道这里，我们预处理的时候可以保证表示和的这个字符串是最长的，否则是无解的）。如果已被赋值，自然只能取那个值，对于不存在这一位的情况同已被赋值类似，看作是0就可以了。如果没有被赋值，那么我们就要挑和之前的不重复的值赋给这个字符。
在判断z的这一步会提供几个回溯的条件。同上面分析x、y一样，我们也需要把z分为已确定和未确定两种状态来分析。如果z已经确定，那么我们就要看x+y+s的个位是否和z的值相等，如果不等就不用继续搜了，否则就继续向下深搜。如果z未确定，那么我们就要看x+y+s的个位这个值是否已被赋给其他字符，如果已经赋给别的字符了，那么就不用继续搜了，如果没有赋给其他字符，就把这个值赋给z这个字符，然后继续向下深搜。
在所有的字符都被赋值完成之后，我们还要判断一下，剩余的余数是否为0，以及有没有某个字符串最高位是0的情况，如果都满足题意就把计数的cnt自加1。如果此后cnt变为了2，那么就必然有多解，同时我们也没有必要去找更多的解了，直接不断return把所有dfs结束即可。
#include<stdio.h>
#include<string.h>
char str[50], a[15], b[15], c[15];
int A, B, C, v[128], num[128], cnt, vis[15][128], hash[15];
void init()
{
int i, j, k, x, y, z;
A = strchr(str, '+') - str;
B = strchr(str, '=') - strchr(str, '+') - 1;
C = strlen(str) - (strchr(str, '=') - str) - 1;
x = y = z = 0;
for(i = 0, j = A - 1; str[i] != '+'; i ++, j --)
{
a[j] = str[i];
if(str[i + 1] != '+' && v[str[i + 1]] > v[str[i]])
x -= v[str[i]];
else
x += v[str[i]];
}
for(++ i, j = B - 1; str[i] != '='; i ++, j --)
{
b[j] = str[i];
if(str[i + 1] != '=' && v[str[i + 1]] > v[str[i]])
y -= v[str[i]];
else
y += v[str[i]];
}
for(++ i, j = C - 1; str[i]; i ++, j --)
{
c[j] = str[i];
if(str[i + 1] && v[str[i + 1]] > v[str[i]])
z -= v[str[i]];
else
z += v[str[i]];
}
if(x + y == z)
printf("Correct ");
else
printf("Incorrect ");
}
int dfs(int cur, int s)
{
int i, j, k, x, y, z, unx, uny, unz;
if(cur == C)
{
if(s == 0 && num[a[A - 1]] != 0 && num[b[B - 1]] != 0 && num[c[C - 1]] != 0)
{
++ cnt;
if(cnt >= 2)
return 1;
}
return 0;
}
z = 0;
unx = 1;
if(cur >= A)
{
x = 0;
unx = 0;
}
else if(num[a[cur]] != -1)
{
x = num[a[cur]];
unx = 0;
}
for(i = (unx ? 0 : 9); i < 10; i ++)
{
if(unx && hash[i])
continue;
if(unx)
{
hash[i] = 1;
x = num[a[cur]] = i;
}
uny = 1;
if(cur >= B)
{
y = 0;
uny = 0;
}
else if(num[b[cur]] != -1)
{
y = num[b[cur]];
uny = 0;
}
for(j = (uny ? 0 : 9); j < 10; j ++)
{
if(uny && hash[j])
continue;
if(uny)
{
hash[j] = 1;
y = num[b[cur]] = j;
}
unz = 1;
if(num[c[cur]] != -1)
unz = 0;
z = (x + y + s) % 10;
k = (x + y + s) / 10;
if(unz)
{
if(!hash[z])
{
hash[z] = 1;
num[c[cur]] = z;
if(dfs(cur + 1, k))
return 1;
hash[z] = 0;
num[c[cur]] = -1;
}
}
else
{
if(z == num[c[cur]])
{
if(dfs(cur + 1, k))
return 1;
}
}
if(uny)
{
hash[j] = 0;
num[b[cur]] = -1;
}
}
if(unx)
{
hash[i] = 0;
num[a[cur]] = -1;
}
}
return 0;
}
void solve()
{
int i, j, k;
if(A > C || B > C)
{
printf("impossible\n");
return ;
}
memset(num, -1, sizeof(num));
memset(hash, 0, sizeof(hash));
cnt = 0;
dfs(0, 0);
if(cnt == 0)
printf("impossible\n");
else if(cnt == 1)
printf("valid\n");
else
printf("ambiguous\n");
}
int main()
{
v['I'] = 1, v['X'] = 10, v['C'] = 100, v['M'] = 1000;
v['V'] = 5, v['L'] = 50, v['D'] = 500;
for(;;)
{
gets(str);
if(str[0] == '#')
break;
init();
solve();
}
return 0;
}