本文共 1260 字，大约阅读时间需要 4 分钟。
题目：
题意：
一共有n层楼，在第i层可以往上或往下$k_i$层。
问从$a$层到$b$层至少需要多少乘多少次电梯。
思路：
bfs
用vis标记当前层是否已访问过，如果是就不再重新入队因为肯定会循环。
要注意判断一下加或减层数时会不会越界。
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 12 #define inf 0x7fffffff13 using namespace std;14 typedef long long LL;15 typedef pair pr;16 17 const int maxn = 505;18 int n, a, b;19 int go[maxn];20 int vis[maxn];21 22 int main()23 {24 scanf("%d%d%d", &n, &a, &b);25 for(int i = 1; i <= n; i++){26 scanf("%d", &go[i]);27 }28 29 queue que;30 que.push(make_pair(a, 0));31 int ans = -1;32 while(!que.empty()){33 pr now = que.front();que.pop();34 if(now.first == b){35 ans = now.second;36 break;37 }38 if(now.first - go[now.first] > 0 && !vis[now.first - go[now.first]]){39 que.push(make_pair(now.first - go[now.first], now.second + 1));40 vis[now.first - go[now.first]] = true;41 }42 if(now.first + go[now.first] <= n && !vis[now.first + go[now.first]]){43 que.push(make_pair(now.first + go[now.first], now.second + 1));44 vis[now.first + go[now.first]] = true;45 }46 }47 printf("%d\n", ans); 48 49 return 0;50 }
转载于:https://www.cnblogs.com/wyboooo/p/10394586.html