求助大佬
by Wangyuqi2010 @ 2024-02-25 15:03:09
32行的```step[nf1]=step[nf]++;```这条语句与```step[nf1]=step[nf], step[nf]++;```等价,可以改成```step[nf1]=step[nf] + 1;```
37行同理
还有30行的```nf1>1```应改成```nf1>=1```,35行同理
@[Wangyuqi2010](/user/1016748)
by lcy666666 @ 2024-02-25 15:14:30
@[Wangyuqi2010](/user/1016748) 当然这样只能过样例,如果能到终点(```nf==b```)应该立刻结束,同时要判断到底能不能到b,可以将step[b]提前初始化为-1
by lcy666666 @ 2024-02-25 15:19:34
先说主要问题:
第一,您 32 行和 37 行的意思不对,相当于 `step[nf2] = step[nf], step[nf]++`,也就是说,使得当前楼层的最小步数增加了1,目标楼层不变,这显然不对,改法见楼上
第二,30 行及 35 行越界判断应当是 `>= 1`,因为 `==1` 也在范围内
第三,bfs() 实现应当用队列……
哪里有用 stack 实现的 bfs() 啊,那就是说它拥有 dfs() 的时间复杂度和 bfs() 空间复杂度,可谓是集百家之短,无一己之长,这题完全卡死了 dfs() 的时间,必须保证第一次直接搜到最优解,也就是使用常规 bfs()
第四,memset() 不建议使用,因为有的时候它初始化的值非常玄学,建议手写循环初始化
第五,40 行的 else continue; 没有必要
以上是我现在发现的问题,如果还有我接着说
by masonxiong @ 2024-02-25 15:30:01
# 自己理解
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 205;
int dis[N], d[N];
bool vis[N];
int main() {
int n, A, B;
cin >> n >> A >> B;
for (int i = 1; i <= n; ++ i) cin >> d[i];
memset(dis, 0x3f, sizeof dis);
queue<int> q;
q.push(A);
vis[A] = 1;
dis[A] = 0;
while (! q.empty()) {
int u = q.front();
q.pop();
int v = u - d[u];
if (v >= 1 && !vis[v]) {
vis[v] = 1;
dis[v] = dis[u] + 1;
q.push(v);
}
v = u + d[u];
if (v <= n && !vis[v]) {
vis[v] = 1;
dis[v] = dis[u] + 1;
q.push(v);
}
}
printf("%d\n", dis[B] == 0x3f3f3f3f ? -1 : dis[B]);
return 0;
}
by ldmahesen20130713 @ 2024-02-25 15:39:31
okk 谢谢各位大佬
by Wangyuqi2010 @ 2024-02-25 15:42:47
各位,还是错怎么办?
```cpp
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
struct coord {
int floor,num;
};
coord s[201];
int step[201];
bool flag[201];
int n,a,b;
queue<coord>q;
int main() {
memset(flag,true,sizeof(flag));
memset(step,-1,sizeof(step));
cin>>n>>a>>b;
for(int i=1; i<=n; i++) {
cin>>s[i].num;
s[i].floor=i;
}
step[a]=0;
flag[a]=false;
q.push(s[a]);
//bfs部分
while(!q.empty()) {
coord now=q.back();
q.pop();
int nf=now.floor,nu=now.num;
//------
int nf1=nf-nu;
int nf2=nf+nu;
if(nf1>=1&&flag[nf1]) {
q.push(s[nf1]);
step[nf1]=step[nf] + 1;
flag[nf]=false;
}
if(nf2<n&&flag[nf2]) {
q.push(s[nf2]);
step[nf2]=step[nf] + 1;
flag[nf]=false;
}
if(nf==b){
cout<<step[b];
return 0;
}
}
cout<<step[b];
return 0;
}
```
by Wangyuqi2010 @ 2024-02-25 16:12:26