一、背景

正常阅读一下题面即可，有一个小的点需要注意一下，* 的字典序默认就是比 0 要小的，所以，在代码中，关于排序的部分，其实不需要我们去注意多余的事项。

二、代码注释

// UVa12107 Digit Puzzle
// 陈锋
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <unordered_map>
#include <unordered_set>
#include <valarray>
#include <vector>

using namespace std;
#define _for(i, a, b) for (int i = (a); i < (b); ++i)
#define _rep(i, a, b) for (int i = (a); i <= (b); ++i)

/*
    Expression，表达式
*/
struct Exp {
    string A[3];  // 整体的式子

    /*
        这里之所以要重载这个 < 运算符，是因为如果最终符合条件的结果有多个的话，那么，
        最后要取字母序最小的那一个
    */
    bool operator<(const Exp& exp) const {
        _for(i, 0, 3) {
            if (A[i] != exp.A[i]) {
                return A[i] < exp.A[i];  // 由于默认的情况下，字符 * 的字典序就是小于字符 0 的，所以，这里就无须做多余的操作
            }
        }
        return false;  // 这是二者相等的情况
    }
};

/*
    A[0]: 第一个因子
    A[1]: 第二个因子
    A[2]: 结果
*/
ostream& operator<<(ostream& os, const Exp& ce) { return os << ce.A[0] << " " << ce.A[1] << " " << ce.A[2]; }

typedef long long LL;

map<Exp, int> SolCnt;  // solution count，存放的是当前的这个式子有几种解法

/*
    每一轮都会产生两种新的变化，所以，这个的时间复杂度是 2 的幂次
*/
void dfsGen(Exp& e, int cur, int pos) {
    if (cur == 3) return;                          // cur 最大是 2，因为表达式中最多有三个字符串
    auto back = e.A[cur][pos];                     // 记录下来以便后面回溯
    int nCur = cur + (pos + 1) / e.A[cur].size();  // next cursor，向后跳一位
    int nPos = (pos + 1) % e.A[cur].size();        // next position，向后跳一位

    dfsGen(e, nCur, nPos);  // 第一种情况，(cur, pos) 没有被改变时，递归
    e.A[cur][pos] = '*';    // 把当前位置替换成 *
    ++SolCnt[e];            // 这是关键之处，如果上面的
    dfsGen(e, nCur, nPos);  // 第二种情况，(cur, pos) 被改变时，递归
    e.A[cur][pos] = back;   // 复原
}

/*
    一次性把每一个谜题所拥有的解法的次数给生成出来，
    然后把结果记入 SolCnt 中，以便后面的整个题目的主 dfs 使用来判断其变化后的谜题是否是有效的
*/
void generate() {
    Exp e;
    _for(a, 1, 100) {
        _for(b, 1, 100) {
            e.A[0] = to_string(a), e.A[1] = to_string(b), e.A[2] = to_string(a * b);
            // Exp ce = e;
            dfsGen(e, 0, 0);
        }
    }
}

const string CH = "*0123456789";

void dfs(const int c, const int maxc, Exp& e, int cur, int pos, bool& found, Exp& ans) {
    if (found && ans < e) return;
    if (SolCnt.count(e) && SolCnt[e] == 1) {
        if (!found) found = true, ans = e;
        if (e < ans) ans = e;
        return;
    }
    if (cur >= 3) return;

    int nCur = cur + (pos + 1) / e.A[cur].size();  // next cursor
    int nPos = (pos + 1) % (e.A[cur].size());      // next position
    const char bk = e.A[cur][pos];                 // backup，以便后面回溯
    for (auto cd : CH) {
        if ((cd == '0' && pos == 0)) continue;
        e.A[cur][pos] = cd;
        int nc = c + (cd != bk);  // current change times
        if (nc <= maxc) dfs(nc, maxc, e, nCur, nPos, found, ans);
        e.A[cur][pos] = bk;  // 恢复
    }
}

int main() {
    // 重定向输入
    freopen("./test_cases/uva12107v2.txt", "r", stdin);

    generate();

    Exp E;

    for (int t = 1; cin >> E.A[0] && E.A[0] != "0"; t++) {  // 读入第一个部分
        cin >> E.A[1] >> E.A[2];                            // 读入第二个和第三个部分
        cout << "Case " << t << ": ";
        _rep(maxc, 0, 8) {  // [0,8]
            Exp ce = E, ans;
            bool found = false;
            dfs(0, maxc, ce, 0, 0, found, ans);  // 修改 maxc 个步骤，这意味着在此次的 dfs 以及其递归进去的部分的修改的操作不可以超过 maxc 次
            if (found) {
                cout << ans;
                break;
            }
        }
        cout << endl;
    }
    return 0;
}
// 19507094	12107	Digit Puzzle	Accepted	C++11	1.960	2017-06-11 12:50:30

三、关键点理解

其实上面的代码注释已经把该讲的内容都讲完了。

这里稍微再捋一下其整体的思路。首先是 generate 一下所有谜题的解的个数，然后开始本题主要的 dfs，回溯一下即可。

多说几句，如果是想让代码为他人理解的话，那么，在进行变量声明的时候，最好还是把变量的声明给独立开来，也就是说，一行最好只声明一个变量。然后就是，这个代码真是一点注释都没有呀。还有就是，这里的 generate 的速度似乎有待改进，每一次运行的时候，一开始执行 generate 的时候应该是花费了不少的时间的。