2023 信奥赛 C++ 提高组 CSP-S 复赛真题：密码锁

题目描述

小 Y 有一把五个拨圈的密码锁。如图所示，每个拨圈上是从 0 到 9 的数字。每个拨圈都可以独立旋转，或者与相邻拨圈联动。

每次操作可以选择一个拨圈将其数字加 1 或减 1（模 10），或者选择两个相邻拨圈同时操作。目标是使所有拨圈变为指定目标数字。

给定初始状态和目标状态，求最少需要多少次操作。

输入格式

一行包含 5 个整数，表示初始状态。 下一行包含 5 个整数，表示目标状态。

输出格式

输出一个整数，表示最少操作次数。

解题思路

本题属于典型的广度优先搜索（BFS）问题。由于拨圈数量较少（5 个），每个位置有 10 种可能，总状态空间为 $10^5$，可以通过 BFS 遍历所有可达状态。

1. 状态表示：使用字符串或数组存储当前 5 个拨圈的数字。
2. 队列管理：将初始状态加入队列，记录步数。
3. 去重标记：使用哈希表或数组记录已访问状态，避免重复计算。
4. 扩展规则：对当前状态的每个拨圈尝试 +1、-1 操作，若达到目标则返回步数。

参考代码

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <unordered_set>
using namespace std;

int main() {
    string start, target;
    cin >> start >> target;
    
    queue<pair<string, int>> q;
    unordered_set<string> visited;
    
    q.push({start, 0});
    visited.insert(start);
    
    while (!q.empty()) {
        auto [curr, steps] = q.front();
        q.pop();
        
        if (curr == target) {
            cout << steps << endl;
            return 0;
        }
        
        for (int i = 0; i < 5; ++i) {
            // 尝试 +1
            string next = curr;
            next[i] = (next[i] - '0' + 1) % 10 + '0';
            if (visited.find(next) == visited.end()) {
                visited.insert(next);
                q.push({next, steps + 1});
            }
            // 尝试 -1
            next = curr;
            next[i] = (next[i] - '0' + 9) % 10 + '0';
            if (visited.find(next) == visited.end()) {
                visited.insert(next);
                q.push({next, steps + 1});
            }
        }
    }
    return 0;
}

总结

密码锁问题通过状态压缩和 BFS 可以高效求解。注意处理边界情况如数字回绕（9+1=0）。