題意：給你一個字謎，讓你改最少的數，使等式有唯一解。

分析：兩次dfs，一次枚舉改動，一次枚舉所有解，判斷是否有且僅有一個解。

#include<cstdio> #include<cctype> #include<string> #include<string.h> #include<queue> #include<math.h> #include<iostream> #include<map> using namespace std; string s[3]; int len[3]; int maxd; char change[11] = { '*','0','1','2','3','4','5','6','7','8','9' }; int stoint() {char cs[10];char ss[10];int t0 = 0, t1 = 0, t2;for (int i = 0; i < len[0]; i++)t0 = t0 * 10 + s[0][i] - '0';for (int i = 0; i < len[1]; i++)t1 = t1 * 10 + s[1][i] - '0';t2 = t0 * t1;for (int i = 0; i < len[2]; i++) {cs[len[2] - i - 1] = t2 % 10 + '0';t2 /=10;}if (t2 != 0 || cs[0] == '0')return 0;//判斷是否存在，滿足位數for (int i = 0; i < len[2]; i++) {if (s[2][i] != '*'&&cs[i] != s[2][i])return 0;}return 1; } int judge(int a, int b) {int ans = 0;if (a == 2) { ans = stoint(); return ans; }int aa, bb;char temp = s[a][b];if (b == len[a] - 1) {aa = a + 1;bb = 0;;}else {aa = a;bb = b + 1;}if (s[a][b] == '*') {for (int i = 1; i < 11; i++) {if (b == 0 && i == 1)continue;s[a][b] = change[i];ans += judge(aa, bb);if (ans > 1)break;}}else {ans += judge(aa, bb);}s[a][b] = temp;return ans; } int dfs(int layer,int indexs,int d) { // if (change > maxd)return false;int ans;if (d == maxd) {ans = judge(0, 0);if (ans==1) return 1;else return 0;}if (layer >= 3)return 0;int a, b;char temp = s[layer][indexs];if (indexs == len[layer] - 1) {//更新坐標a = layer + 1;b = 0;}else {a = layer;b = indexs + 1;}bool ok = false;for (int i = 0; i < 11; i++) {if (b == 0 && i == 1)continue;//前導0；if (temp == change[i]) {//相同的排除s[layer][indexs] = temp;ans=dfs(a, b, d);}else {s[layer][indexs] = change[i];ans = dfs(a, b, d + 1);}if (ans)break;}if (!ans)s[layer][indexs] = temp;//沒找到，還原return ans; }int main() {int kase = 0;while (cin >> s[0] && s[0][0] != '0') {cin >> s[1] >> s[2];for (int i = 0; i < 3; i++)len[i] = s[i].length();for (maxd = 0; ; maxd++) {if (dfs(0,0, 0))break;}cout << "Case " << ++kase<<": ";cout << s[0] << " " << s[1] << " " << s[2] << endl;}//system("pause");return 0;}

?

總結

以上是生活随笔為你收集整理的UVA12107Digit Puzzle数字字谜（迭代加深搜索）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。