学习目标
- 用队列按距离分层扩展位置，求单位代价转移的最少步数。
- 入队时标记访问，避免重复入队。
- 处理起终点相同、位置为零和范围边界。
前置知识与环境
建议先学习第 2 章栈与队列。使用 ISO C++17；开始前可在本目录运行 make doctor。
任务
农夫位于 start，牛位于 target。每一步可从位置 x 移到 x-1、x+1 或 2*x，但只能到合法位置。求最少步数；三种移动代价都为 1，队列按层访问即可保证第一次到达目标时距离最短。
输入格式
一行 start target limit，三者均为整数；合法位置为 0..limit-1。
输出格式
输出从 start 到 target 的最少步数并换行。例如 5 17 100 可沿 5→4→8→16→17 用 4 步到达，答案为 4。
数据范围与限制
- 输入规模不超过
200000，除题面另有说明外整数使用 64 位有符号范围。 1 <= limit <= 200000，且0 <= start,target < limit；三种移动分别为x-1、x+1、2*x，越界移动忽略。- 标准输出只保留题目要求的结果；调试信息写入标准错误。
- 目标算法应为线性或摊还线性时间，辅助空间不超过
O(n)。
边界与验收重点
start=target时为 0 步；limit=1只有位置 0。- 跳过
x-1<0、x+1>=limit或2*x>=limit的移动。 - 遇到已访问位置不再重复入队；向后走
x-1有时是最优路径的一部分。
如何验证
powershell
make doctor
make run
make score未安装 Make 时，在仓库根目录运行：
powershell
pnpm lab:validate -- labs/chapter-02/exercise/E-02-14-farmer-cow-bfs
pnpm lab:run -- labs/chapter-02/exercise/E-02-14-farmer-cow-bfs
pnpm lab:score -- labs/chapter-02/exercise/E-02-14-farmer-cow-bfs思考与复盘
- 为什么用栈做深度优先搜索不能保证第一次遇到目标时最短？
- 为什么访问标记应在入队时设置？
思考题参考
- 深度优先会先沿一条路径走远，可能错过另一条更短路径。
- 若等到出队才标记，同一位置可能从多个前驱重复入队。
题解
点击查看题解
思路与不变量
把每个合法位置看成图的一个顶点，x-1、x+1 和 2*x 是三条单位代价边。使用 BFS 队列按距离分层扩展；distance[x] 记录从起点到 x 的最短步数，非 -1 表示该位置已经入队。
算法步骤
- 将
start的距离设为 0 并入队； - 每次取出一个位置，枚举三个转移；
- 忽略越界位置和已经访问的位置，对新位置设置
distance[current] + 1后入队； - 目标位置出队后即可结束，最终输出其距离。
正确性说明
BFS 先处理距离为 0 的顶点，再处理距离为 1、2……的顶点。由于每条边代价相同，某个位置第一次入队时使用的路径已经是最短路径；访问标记在入队时设置也保证它不会被重复加入。因而输出的 distance[target] 是最少步数。
复杂度分析
- 时间复杂度：
O(limit)，每个位置最多出队一次并检查三个转移； - 额外空间：
O(limit)，用于距离数组和队列。
边界注意
start == target直接得到 0；2*x、x-1、x+1都要先检查是否落在0..limit-1；- 不能因为某次向后移动看似变远就删除它，它可能是最短路径的一部分。