# P1588 [USACO07OPEN] Catch That Cow S复盘

P1588 [USACO07OPEN] Catch That Cow S 题解复盘基本信息项目内容题目编号、来源P1588 洛谷 / [USACO07OPEN] Catch That Cow S训练层级B BFS基础知识版块BFS、一维状态搜索解题前・关键信号识别维度分析目标、约束、底层结构目标从起点 x 到终点 y 的最少移动次数每次可走 p1、p-1、2p约束x,y ≤ 100000t ≤ 10底层结构一维数轴上的无权图BFS 求最短路。数据规模坐标范围 100000BFS 单次 O(MAXN)完全可行。候选算法和依据BFS依据每一步代价为 1求最少步数 无权图最短路。复杂度预判时间复杂度 O(MAXN)空间复杂度 O(MAXN)。解题后・外化复盘维度内容实现结构 / 核心思路定义dist[p]表示从起点到位置 p 的最少步数初始dist[x]0。BFS 队列中取出当前点 p对三个可能的下一个位置p-1, p1, 2p进行扩展若未访问且在有效范围内0~100000更新步数并入队。当出队位置等于终点时直接返回步数BFS 首次到达即最优。错因回溯1. 未限制坐标范围0≤p≤100000导致 2p 可能溢出或访问负坐标2. 用 DFS 导致栈溢出或无法保证最短路3. 忘记初始化 dist 数组每组数据需重置。边界和易错点1. 坐标范围0 ≤ pos ≤ 100000超出范围直接跳过2. 起点可能大于终点但 BFS 仍会搜索通过 p-1 逐步减小3. 使用memset初始化 -1。下次看到什么信号我应该想到这个方法看到「一维数轴 三种固定操作 求最少步数」用 BFS。AC 完整代码按你提供的代码#includebits/stdc.husingnamespacestd;constintMAXN100000;intdista[MAXN5];intbfs(intx,inty){memset(dista,-1,sizeof(dista));queueintq;q.push(x);dista[x]0;while(!q.empty()){intpq.front();q.pop();if(py)returndista[p];intnext[3]{p-1,p1,p*2};for(inti0;i3;i){intnpnext[i];if(np0||npMAXN)continue;if(dista[np]!-1)continue;dista[np]dista[p]1;q.push(np);}}return-1;}intmain(){intt;cint;while(t--){intx,y;cinxy;coutbfs(x,y)endl;}return0;}