1
回溯的通用范式：
2
┌─────────────────────────────────────────────┐
3
│ void backtrack(路径, 选择列表) {              │
4
│     if (满足结束条件) {                       │
5
│         记录答案;                             │
6
│         return;                              │
7
│     }                                        │
8
│                                              │
9
│     for (选择 in 选择列表) {                  │
10
│         if (选择不合法) continue;  ← 剪枝      │
11
│         做选择;                               │
12
│         backtrack(路径, 新的选择列表);         │
13
│         撤销选择;  ← 回溯                     │
14
│     }                                        │
15
│ }                                            │
16
└─────────────────────────────────────────────┘

1
// 标准 BFS：层序遍历
2
int bfs(const std::vector<std::vector<int>>& graph, int start, int target) {
3
    int n = graph.size();
4
    std::vector<bool> visited(n, false);
5
    std::queue<std::pair<int, int>> q;  // {node, distance}
6
    q.push({start, 0});
7
    visited[start] = true;
8

9
    while (!q.empty()) {
10
        auto [node, dist] = q.front(); q.pop();
11
        if (node == target) return dist;
12

13
        for (int next : graph[node]) {
14
            if (!visited[next]) {
15
                visited[next] = true;
16
                q.push({next, dist + 1});
17
            }
18
        }
19
    }
20
    return -1;
21
}

1
// Dijkstra：贪心松弛
2
std::vector<int> dijkstra(const std::vector<std::vector<std::pair<int,int>>>& graph,
3
                          int start) {
4
    int n = graph.size();
5
    std::vector<int> dist(n, INT_MAX);
6
    dist[start] = 0;
7

8
    using State = std::pair<int, int>;  // {distance, node}
9
    std::priority_queue<State, std::vector<State>, std::greater<State>> pq;
10
    pq.push({0, start});
11

12
    while (!pq.empty()) {
13
        auto [d, node] = pq.top(); pq.pop();
14
        if (d > dist[node]) continue;  // ⚠️ 懒惰删除
15

16
        for (auto& [next, weight] : graph[node]) {
17
            int newDist = d + weight;
18
            if (newDist < dist[next]) {
19
                dist[next] = newDist;
20
                pq.push({newDist, next});
21
            }
22
        }
23
    }
24
    return dist;
25
}

1
// A* 在网格上的实现：从 (sr,sc) 到 (tr,tc)
2
struct AStarState {
3
    int r, c;
4
    int g;  // 已走步数
5
    int h;  // 启发式：曼哈顿距离
6
    int f() const { return g + h; }
7

8
    bool operator>(const AStarState& other) const {
9
        return f() > other.f();  // 优先队列按 f 值
10
    }
11
};
12

13
int aStar(const std::vector<std::vector<int>>& grid,
14
          int sr, int sc, int tr, int tc) {
15
    int m = grid.size(), n = grid[0].size();
16
    int dirs[] = {0, 1, 0, -1, 0};
17

18
    auto heuristic = [&](int r, int c) {
19
        return std::abs(r - tr) + std::abs(c - tc);  // 曼哈顿距离
20
    };
21

22
    std::vector<std::vector<int>> bestG(m, std::vector<int>(n, INT_MAX));
23
    std::priority_queue<AStarState, std::vector<AStarState>,
24
                        std::greater<AStarState>> pq;
25

26
    pq.push({sr, sc, 0, heuristic(sr, sc)});
27
    bestG[sr][sc] = 0;
28

29
    while (!pq.empty()) {
30
        auto [r, c, g, h] = pq.top(); pq.pop();
31

32
        if (r == tr && c == tc) return g;
33

34
        if (g > bestG[r][c]) continue;  // 懒惰删除
35

36
        for (int d = 0; d < 4; ++d) {
37
            int nr = r + dirs[d], nc = c + dirs[d + 1];
38
            if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
39
            if (grid[nr][nc] == 1) continue;  // 障碍物
40

41
            int ng = g + 1;
42
            if (ng >= bestG[nr][nc]) continue;
43

44
            bestG[nr][nc] = ng;
45
            pq.push({nr, nc, ng, heuristic(nr, nc)});
46
        }
47
    }
48
    return -1;
49
}

1
std::vector<std::string> letterCombinations(std::string digits) {
2
    if (digits.empty()) return {};
3

4
    const std::vector<std::string> mapping = {
5
        "", "", "abc", "def", "ghi", "jkl",
6
        "mno", "pqrs", "tuv", "wxyz"
7
    };
8

9
    std::vector<std::string> result;
10
    std::string path;
11

12
    std::function<void(int)> backtrack = [&](int idx) {
13
        if (idx == digits.size()) {
14
            result.push_back(path);
15
            return;
16
        }
17

18
        for (char c : mapping[digits[idx] - '0']) {
19
            path.push_back(c);
20
            backtrack(idx + 1);
21
            path.pop_back();
22
        }
23
    };
24

25
    backtrack(0);
26
    return result;
27
}

1
// 欧拉路径问题：找到字典序最小的"用完所有机票"的行程
2
// 回溯 + Hierholzer 算法
3
std::vector<std::string> findItinerary(
4
    std::vector<std::vector<std::string>>& tickets) {
5

6
    // 构建邻接表（按字典序）
7
    std::unordered_map<std::string,
8
        std::priority_queue<std::string, std::vector<std::string>,
9
                            std::greater<std::string>>> graph;
10

11
    for (auto& t : tickets) {
12
        graph[t[0]].push(t[1]);
13
    }
14

15
    std::vector<std::string> result;
16

17
    std::function<void(const std::string&)> dfs =
18
        [&](const std::string& airport) {
19
        auto& neighbors = graph[airport];
20
        while (!neighbors.empty()) {
21
            std::string next = neighbors.top();
22
            neighbors.pop();
23
            dfs(next);
24
        }
25
        result.push_back(airport);  // 后序加入！
26
    };
27

28
    dfs("JFK");
29
    std::reverse(result.begin(), result.end());  // 反转得到正序
30
    return result;
31
}

1
// 2x3 的滑块拼图，求最少步数 → A* 或 BFS
2
int slidingPuzzle(std::vector<std::vector<int>>& board) {
3
    // 将 2x3 展平为字符串，更方便操作
4
    std::string start;
5
    for (int r = 0; r < 2; ++r)
6
        for (int c = 0; c < 3; ++c)
7
            start += ('0' + board[r][c]);
8

9
    std::string target = "123450";
10

11
    // 每个位置可交换的邻居索引（2x3 网格）
12
    std::vector<std::vector<int>> neighbors = {
13
        {1, 3},       // 0
14
        {0, 2, 4},    // 1
15
        {1, 5},       // 2
16
        {0, 4},       // 3
17
        {1, 3, 5},    // 4
18
        {2, 4}        // 5
19
    };
20

21
    // 启发式：曼哈顿距离（每个数字到目标位置的距离之和）
22
    auto heuristic = [&](const std::string& state) {
23
        int h = 0;
24
        for (int i = 0; i < 6; ++i) {
25
            if (state[i] == '0') continue;
26
            int num = state[i] - '1';
27
            h += std::abs(i / 3 - num / 3) + std::abs(i % 3 - num % 3);
28
        }
29
        return h;
30
    };
31

32
    using State = std::tuple<int, int, std::string>;  // {f, g, state}
33
    std::priority_queue<State, std::vector<State>, std::greater<State>> pq;
34

35
    std::unordered_map<std::string, int> bestG;
36
    int startH = heuristic(start);
37
    pq.push({startH, 0, start});
38
    bestG[start] = 0;
39

40
    while (!pq.empty()) {
41
        auto [f, g, state] = pq.top(); pq.pop();
42
        if (state == target) return g;
43
        if (g > bestG[state]) continue;
44

45
        int zeroPos = state.find('0');
46
        for (int next : neighbors[zeroPos]) {
47
            std::string nextState = state;
48
            std::swap(nextState[zeroPos], nextState[next]);
49

50
            int ng = g + 1;
51
            if (bestG.count(nextState) && ng >= bestG[nextState]) continue;
52

53
            bestG[nextState] = ng;
54
            pq.push({ng + heuristic(nextState), ng, nextState});
55
        }
56
    }
57
    return -1;
58
}

1
// N 个技能，找 K 个技能的最优连招（考虑释放顺序 → 排列）
2
// 用于战斗系统的技能推荐
3
struct Skill {
4
    int id;
5
    int damage;
6
    int cooldown;
7
    std::vector<int> synergy;  // 与其他技能的联动加成
8
};
9

10
void findBestCombo(const std::vector<Skill>& skills, int k,
11
                   std::vector<int>& bestCombo, int& bestDamage) {
12
    std::vector<int> path;
13
    std::vector<bool> used(skills.size(), false);
14

15
    std::function<void(int, int)> backtrack = [&](int steps, int totalDmg) {
16
        if (steps == k) {
17
            if (totalDmg > bestDamage) {
18
                bestDamage = totalDmg;
19
                bestCombo = path;
20
            }
21
            return;
22
        }
23

24
        // 最优性剪枝：即使后面都选最大伤害也不可能超过当前最优
25
        int maxPossible = totalDmg + (k - steps) * maxSkillDamage;
26
        if (maxPossible <= bestDamage) return;
27

28
        for (int i = 0; i < skills.size(); ++i) {
29
            if (used[i]) continue;
30

31
            int bonus = 0;
32
            if (!path.empty()) {
33
                for (int prev : skills[path.back()].synergy) {
34
                    if (prev == skills[i].id) bonus += 50;  // 联动加成
35
                }
36
            }
37

38
            used[i] = true;
39
            path.push_back(i);
40
            backtrack(steps + 1, totalDmg + skills[i].damage + bonus);
41
            path.pop_back();
42
            used[i] = false;
43
        }
44
    };
45

46
    backtrack(0, 0);
47
}

1
// 简化版 Minimax + Alpha-Beta 剪枝（井字棋）
2
// 这是游戏 AI 的核心技术
3
int alphaBeta(std::vector<std::vector<char>>& board, int depth,
4
              int alpha, int beta, bool isMaximizing) {
5
    int score = evaluate(board);  // 评估当前局面
6
    if (std::abs(score) >= 1000 || depth == 0) return score;
7
    if (isDraw(board)) return 0;
8

9
    if (isMaximizing) {
10
        int maxEval = -9999;
11
        for (auto& move : getMoves(board)) {
12
            makeMove(board, move, 'X');
13
            int eval = alphaBeta(board, depth - 1, alpha, beta, false);
14
            undoMove(board, move);
15
            maxEval = std::max(maxEval, eval);
16
            alpha = std::max(alpha, eval);
17
            if (beta <= alpha) break;  // β 剪枝！
18
        }
19
        return maxEval;
20
    } else {
21
        int minEval = 9999;
22
        for (auto& move : getMoves(board)) {
23
            makeMove(board, move, 'O');
24
            int eval = alphaBeta(board, depth - 1, alpha, beta, true);
25
            undoMove(board, move);
26
            minEval = std::min(minEval, eval);
27
            beta = std::min(beta, eval);
28
            if (beta <= alpha) break;  // α 剪枝！
29
        }
30
        return minEval;
31
    }
32
}

1
// 战棋游戏中，计算角色在 N 步内能到达的所有位置
2
// 考虑地形消耗（平原=1，森林=2，山地=3，不可通过=∞）
3
std::vector<std::vector<int>> getMovementRange(
4
    const std::vector<std::vector<int>>& terrain,
5
    int startR, int startC, int maxSteps) {
6

7
    int m = terrain.size(), n = terrain[0].size();
8
    std::vector<std::vector<int>> cost(m, std::vector<int>(n, INT_MAX));
9

10
    // Dijkstra 搜索（带权移动）
11
    using State = std::tuple<int, int, int>;  // {cost, r, c}
12
    std::priority_queue<State, std::vector<State>, std::greater<State>> pq;
13
    pq.push({0, startR, startC});
14
    cost[startR][startC] = 0;
15

16
    int dirs[] = {0, 1, 0, -1, 0};
17

18
    while (!pq.empty()) {
19
        auto [c, r, col] = pq.top(); pq.pop();
20
        if (c > cost[r][col]) continue;
21

22
        for (int d = 0; d < 4; ++d) {
23
            int nr = r + dirs[d], nc = col + dirs[d + 1];
24
            if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
25
            if (terrain[nr][nc] < 0) continue;  // 不可通过
26

27
            int newCost = c + terrain[nr][nc];  // 地形消耗
28
            if (newCost > maxSteps) continue;
29
            if (newCost >= cost[nr][nc]) continue;
30

31
            cost[nr][nc] = newCost;
32
            pq.push({newCost, nr, nc});
33
        }
34
    }
35

36
    return cost;  // cost[r][c] <= maxSteps 即可达
37
}