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;}
