1 条题解
-
0
#include <bits/stdc++.h> using namespace std; const int MAXN = 200; queue<int> q; // 存还需要搜索的点 bool vis[MAXN + 5]; // vis[i] 存 i 这个点搜过了没有 int dis[MAXN + 5]; // dis[i] 存从起点几步能走到 i int n, a, b; // 楼层(点的个数)、起点终点 int k[MAXN + 5]; // 第 i 层能走到 i+k[i], i-k[i] int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> a >> b; for (int i = 1; i <= n; i++) cin >> k[i]; // 起点入队 vis[a] = true; dis[a] = 0; q.push(a); // 队列非空且没到终点就继续搜 while (!q.empty() && !vis[b]) { // 取出队头 int now = q.front(); q.pop(); // 考虑 now 能走到哪儿 int nxt; // 下一步到的位置 next // now-k[now],能走到,且没走过 nxt = now - k[now]; if (1 <= nxt && nxt <= n && !vis[nxt]) { vis[nxt] = true; dis[nxt] = dis[now] + 1; q.push(nxt); } // now+k[now],能走到,且没走过 nxt = now + k[now]; if (1 <= nxt && nxt <= n && !vis[nxt]) { vis[nxt] = true; dis[nxt] = dis[now] + 1; q.push(nxt); } } if (!vis[b]) cout << -1; else cout << dis[b]; return 0; }
- 1
信息
- ID
- 579
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 4
- 标签
- (无)
- 递交数
- 22
- 已通过
- 16
- 上传者