BFS ``` #include <iostream> #include <cstring> #include <queue> using namespace std; const int N = 210; int n, a, b; int arr[N], d[N]; int m[2] = {1, -1}; queue<int> q; int bfs(int a, int b) // a, b 为下标(电梯楼层) { q.push(a); d[a] = 0; while (!q.empty()) { int t = q.front(); q.pop(); for (int i = 0; i <= 1; i++) { int nx = t + arr[t] * m[i]; if (nx >= 1 && nx <= n && d[nx] == -1) { d[nx] = d[t] + 1; q.push(nx); } } } return d[b]; } int main() { cin >> n >> a >> b; for (int i = 1; i <= n; i++) cin >> arr[i]; memset(d, -1, sizeof d); cout << bfs(a, b); return 0; } ```

``` int main() { int n, a, b; cin >> n >> a >> b; vector<int> nums(n + 1); for (int i = 1; i <= n; i++) { cin >> nums[i]; } vector<bool> visited(n + 1, false); queue<State> q; q.push(State(a, 0)); visited[a] = true; while (!q.empty()) { State current = q.front(); q.pop(); if (current.floor == b) { cout << current.presses << endl; return 0; } int up = current.floor + nums[current.floor]; int down = current.floor - nums[current.floor]; if (up <= n && !visited[up]) { q.push(State(up, current.presses + 1)); visited[up] = true; } if (down >= 1 && !visited[down]) { q.push(State(down, current.presses + 1)); visited[down] = true; } } cout << -1 << endl; return 0; } ```

``` #include using namespace std; int n,a,b; int k[202]; bool visit[202]={0};//标记数组 int fuhao[3]={0,1,-1}; int flag,sum=0; int ceng=1,jie=0,xia=0;//当前层节点数量，当前层遍历到第几个节点 queue<int> q; void bfs() { q.push(a);//当前楼层进入队列 visit[a]=1; while(!q.empty()){ int c=q.front();//取出队列第一个元素 if(c!=b) q.pop(); else { flag=1;//输出次数 return; } for(int i=1;i<=2;i++) { int d=c+fuhao[i]*k[c]; if(d>=1 && d<=n && !visit[d]) { visit[d]=1; q.push(d); xia++;//记录下一层节点个数 } } jie++; //遍历的节点数加一，直到该层遍历完，层数加一 if(jie==ceng) { ceng=xia; xia=0; jie=0; sum++; } } return; } int main(){ cin>>n>>a>>b; for(int i=1;i<=n;i++){ cin>>k[i]; } flag=0; sum=0; bfs(); if(flag==0){ cout<<-1; } else cout<<sum; return 0; } ```

DFS 最少次数，每次都要更新p数组，初始为正无穷 ```cpp #include <iostream> #include <cstring> using namespace std; const int N = 210; int n, a, b; int d[N]; int p[N]; int flag; void dfs(int u, int level) { p[level] = u; if (level == b) { flag = true; return; } if (level + d[level] <= n && u + 1 < p[level + d[level]]) dfs(u + 1, level + d[level]); if (level - d[level] >= 1 && u + 1 < p[level - d[level]]) dfs(u + 1, level - d[level]); } void solve() { memset(p, 0x3f, sizeof p); cin >> n >> a >> b; for (int i = 1; i <= n; i++) cin >> d[i]; dfs(0, a); if (flag) cout << p[b] << endl; else cout << -1 << endl; } int main() { solve(); system("pause"); return 0; } ```

``` #include <iostream> #include <queue> #include <cstring> #define x first #define y second using namespace std; const int N=210; int g[N]; int st[N]; typedef pair<int,int>PII; int n; void bfs(int start,int end) { queue<PII>q; q.push({start,g[start]}); st[start]=0; while(q.size()) { auto t=q.front(); q.pop(); int a=t.x-g[t.x],b=t.x+g[t.x]; if(a>=1&&st[a]==-1){ q.push({a,g[a]}); st[a]=st[t.x]+1; } if(b<=n&&st[b]==-1){ q.push({b,g[b]}); st[b]=st[t.x]+1; } } } int main() { int a,b; cin>>n>>a>>b; for(int i=1;i<=n;i++) cin>>g[i]; memset(st,-1,sizeof st); bfs(a,b); cout<<st[b]; return 0; } ```

```C++ #include <cstdio> #include <vector> #include <queue> #include <utility> #include <functional> using namespace std; int main() { int n, a, b; scanf("%d %d %d", &n, &a, &b); vector<int> arr(n + 1); for (int i = 1; i <= n; ++i) scanf("%d", &arr[i]); long long res = 1e9; vector<char> ita(n + 1, 0); // dfs 好像不行, 这样只有80分 // long long now = 0; // function<void(int)> dfs = [&](int i) { // 递归爆炸 // if (i <= 0 || i > n || ita[i]) // return; // // if (i == b) { // res = min(res, now); // return; // } // // ++now; // ita[i] = 1; // dfs(i + arr[i]); // dfs(i - arr[i]); // ita[i] = 0; // --now; // }; queue<pair<int, long long>> Q; // 当前是第几层 , 操作次数 Q.push({a, 0}); while (Q.size()) { auto x = Q.front(); int cen = x.first; long long cs = x.second; Q.pop(); if (cen == b) { res = cs; break; } if (cen + arr[cen] <= n && !ita[cen + arr[cen]]) { ita[cen + arr[cen]] = 1; Q.push({cen + arr[cen], cs + 1}); } if (cen - arr[cen] > 0 && !ita[cen - arr[cen]]) { ita[cen - arr[cen]] = 1; Q.push({cen - arr[cen], cs + 1}); } } // dfs(a); printf("%lld\n", res == 1e9 ? -1 : res); return 0; } ```