P1135 奇怪的电梯 题解复盘基本信息项目内容题目编号、来源P1135 洛谷 / 奇怪的电梯训练层级B BFS基础知识版块BFS、状态搜索、一维最短路解题前・关键信号识别维度分析目标、约束、底层结构目标从 A 楼到 B 楼的最少按键次数约束N ≤ 200底层结构把每一层楼看作一个节点从 i 层可以到达 iK[i] 层和 i-K[i] 层求无权图最短路。数据规模N ≤ 200BFS 完全可行。候选算法和依据BFS依据求最少步数 无权图最短路用 BFS 逐层扩散。复杂度预判时间复杂度 O(N)空间复杂度 O(N)。解题后・外化复盘维度内容实现结构 / 核心思路第一步用mapint,int m存储每层楼的数字也可用数组第二步定义v[205]记录到达每层楼的最少按键次数初始化为 -1第三步从起点 A 开始 BFS队列存储楼层号第四步每次取出队首 x计算y x m[x]向上和z x - m[x]向下若在 1~N 范围内且未访问则入队并记录v[next] v[x] 1第五步输出v[B]。核心思想把电梯问题转化为一维图上的 BFS 最短路每个节点最多两个分支。错因回溯1. 忘记初始化v数组为 -12. 向上/向下越界判断写错yn和z03. 用 DFS 搜索导致超时或栈溢出4. 没有处理无法到达的情况输出 -1因为v[B]仍为 -1。边界和易错点1.m[i]可能为 0此时向上和向下都到同一层或原地不动需要正确处理2. 起点 A 可能等于终点 B此时答案为 03. 楼层范围是 1~N不是 0~N-14. 入队时立即标记访问。下次看到什么信号我应该想到这个方法看到「最少步数 状态转移固定 图/网格/一维」用 BFS。AC 完整代码按你提供的代码#includeiostream#includecstring#includequeue#includealgorithm#includeset#includevector#includemapusingnamespacestd;intn,a,b;mapint,intm;intv[205];voidbfs(inta){queueintq;memset(v,-1,sizeof(v));q.push(a);v[a]0;while(!q.empty()){intxq.front();q.pop();intyxm[x];intzx-m[x];if(ynv[y]-1){q.push(y);v[y]v[x]1;}if(z0v[z]-1){q.push(z);v[z]v[x]1;}}}intmain(){cinnab;for(inti1;in;i){intx;cinx;m[i]x;}bfs(a);coutv[b]endl;return0;}