洛谷 P1135 题解

题面

奇怪的电梯

解题

一看“至少按几次按钮”，就是个最短路问题。每次按按钮都是等价的，所以是个无权最短路问题，使用 BFS 解决。

要写 BFS，就要想到剪枝。题中说，按钮只在目标楼层存在的情况下可用，这就是一个剪枝条件。

还有一个隐含的条件：如果不能重复到达同一个楼层。

如果重复了，分两种情况（设 A 为起点，C 为终点）：

1. 不可达：如 A -> B -> A，而 A 只能通往 B，B 只能通往 A，此时无解，此方案当然不可能是最优解。
2. 可达：如 A -> B -> A -> C，这一定不是最短路，因为 A 既然可以通往 C，那么 A -> C 是等价且更短的方案，此方案也不可能最优解。

因此，不需要再搜索到达过的楼层。

代码

#include <iostream>
#include <queue>
using namespace std;

const int N = 205;
int n, k[N];
bool vis[N];
queue<int> q;

int bfs(int start, int target) {
  if (start == target) return 0;
  q.push(start);
  int ans = 0;
  while (!q.empty()) {
    int len = q.size();
    ++ans;
    for (int i = 1; i <= len; ++i) {
      int h = q.front();
      q.pop();
      vis[h] = 1;  // 标记已达
      int up = h + k[h], down = h - k[h];
      if (up <= n) {  // 可上
        if (up == target) return ans;
        if (!vis[up]) q.push(up);  // 如果再去到达过的楼层就会循环
      }
      if (down >= 1) {  // 可下
        if (down == target) return ans;
        if (!vis[down]) q.push(down);  // 所以剪枝
      }
    }
  }
  return -1;
}

int main() {
  int a, b;
  cin >> n >> a >> b;
  for (int i = 1; i <= n; ++i) cin >> k[i];
  cout << bfs(a, b);
  return 0;
}