当前位置：首页 > 牛客 > 牛客12546题：广度优先搜索（BFS）解法解决饥饿的小易问题

牛客12546题：广度优先搜索（BFS）解法解决饥饿的小易问题

3小时前

一、题目解读

牛客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) 符合题目规则。