牛客12546题：广度优先搜索（BFS）解法解决饥饿的小易问题
一、题目解读
牛客12546题是一道典型的数学问题，要求通过给定的数学变换规则（即 x -> (4x+3) % MOD 和 x -> (8x+7) % MOD），从初始位置 x0 出发，寻找到达目标位置（即 x % MOD == 0）的最小步数。题目考察了算法设计中的搜索策略与状态优化，需要高效地遍历状态空间并避免重复计算。
二、解题思路
解题的核心在于采用广度优先搜索（BFS）算法。由于题目要求找到最短路径，BFS天然适合解决此类问题：它按层遍历，确保第一次到达目标状态时的步数即为最小步数。
关键在于：
1. 使用队列存储待扩展的状态（位置+步数）。
2. 哈希表（unordered_map）记录已访问位置，避免重复遍历。
3. 对每个位置生成两个子状态，检查合法性后入队。
4. 设置最大步数限制（MAX_STEPS）防止超时，超出则终止搜索。
5. 终止条件：当位置 x 满足 x % MOD == 0 时，立即输出步数。
三、解题步骤
1. 初始化：将初始位置 x0 入队，标记为已访问，步数为0。
2. 循环扩展：
○ 弹出队首元素 (x, steps)。
○ 计算两个新位置 next1 = (4x+3) % MOD 和 next2 = (8x+7) % MOD。
○ 若新位置未被访问且步数未超限，标记并加入队列（步数+1）。
3. 终止判断：若当前位置满足目标条件，输出步数并结束；若队列为空且未找到目标，输出-1。
四、代码与注释
#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;
const long long MOD = 1000000007; // 模数
const int MAX_STEPS = 100000; // 最大步数限制
int main() {
long long x0;
cin >> x0; // 输入初始位置
queue<pair<long long, int>> q; // 存储位置-步数对
unordered_map<long long, bool> visited; // 记录已访问位置
q.push({x0, 0}); // 初始状态入队
visited[x0] = true; // 标记已访问
while (!q.empty()) {
auto current = q.front(); // 获取队首元素
q.pop();
long long x = current.first; // 当前位置
int steps = current.second; // 当前步数
// 目标状态判断
if (x % MOD == 0) {
cout << steps << endl; // 输出最小步数
return 0;
}
// 步数超限，跳过
if (steps >= MAX_STEPS) {
continue;
}
// 生成两个新位置
long long next1 = (4 * x + 3) % MOD;
long long next2 = (8 * x + 7) % MOD;
// 检查并扩展新状态
if (!visited[next1]) {
visited[next1] = true;
q.push({next1, steps + 1});
}
if (!visited[next2]) {
visited[next2] = true;
q.push({next2, steps + 1});
}
}
// 未找到目标，输出-1
cout << -1 << endl;
return 0;
}注释说明：
● MOD 为模数，避免整数溢出。
● MAX_STEPS 限制搜索深度，防止无限循环。
● visited 哈希表优化时间复杂度至O(n)，避免重复计算。
● 双状态生成 (4x+3) 和 (8x+7) 符合题目规则。
五、总结
该解法通过BFS结合哈希表，实现了高效的状态遍历与去重，时间复杂度为O(n)，空间复杂度为O(n)。优化点包括：
1. 明确终止条件，避免无效搜索。
2. 模运算确保状态合法性。
3. 最大步数限制提升鲁棒性。
适用于求解最短路径类问题，为同类算法设计提供了参考模板。
原创内容 转载请注明出处
