P1135 奇怪的电梯复盘-拓冰建站

P1135 奇怪的电梯题解复盘

基本信息

项目	内容
题目编号、来源	P1135 洛谷 / 奇怪的电梯
训练层级	B BFS基础
知识版块	BFS、状态搜索、一维最短路

解题前・关键信号识别

维度	分析
目标、约束、底层结构	目标：从 A 楼到 B 楼的最少按键次数；约束：N ≤ 200；底层结构：把每一层楼看作一个节点，从 i 层可以到达 i+K[i] 层和 i-K[i] 层，求无权图最短路。
数据规模	N ≤ 200，BFS 完全可行。
候选算法和依据	BFS；依据：求最少步数 = 无权图最短路，用 BFS 逐层扩散。
复杂度预判	时间复杂度 O(N)，空间复杂度 O(N)。

解题后・外化复盘

维度	内容
实现结构 / 核心思路	第一步用`map<int,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`数组为 -1；2. 向上/向下越界判断写错（`y<=n`和`z>0`）；3. 用 DFS 搜索导致超时或栈溢出；4. 没有处理无法到达的情况（输出 -1，因为`v[B]`仍为 -1）。
边界和易错点	1.`m[i]`可能为 0，此时向上和向下都到同一层（或原地不动），需要正确处理；2. 起点 A 可能等于终点 B，此时答案为 0；3. 楼层范围是 1~N，不是 0~N-1；4. 入队时立即标记访问。
下次看到什么信号，我应该想到这个方法	看到「最少步数 + 状态转移固定 + 图/网格/一维」，用 BFS。

AC 完整代码（按你提供的代码）

#include<iostream>#include<cstring>#include<queue>#include<algorithm>#include<set>#include<vector>#include<map>usingnamespacestd;intn,a,b;map<int,int>m;intv[205];voidbfs(inta){queue<int>q;memset(v,-1,sizeof(v));q.push(a);v[a]=0;while(!q.empty()){intx=q.front();q.pop();inty=x+m[x];intz=x-m[x];if(y<=n&&v[y]==-1){q.push(y);v[y]=v[x]+1;}if(z>0&&v[z]==-1){q.push(z);v[z]=v[x]+1;}}}intmain(){cin>>n>>a>>b;for(inti=1;i<=n;i++){intx;cin>>x;m[i]=x;}bfs(a);cout<<v[b]<<endl;return0;}