栈空间也是空间哦,而且你这里甚至还允许同一层重复走过
by yummy @ 2024-03-14 12:17:32
@[o_CIHL](/user/1165228) 栈空间也算的哦,你栈开太多了
by monkeyinGD @ 2024-03-14 12:41:11
@[yummy](/user/101694) 原来如此,,感谢感谢
by o_CIHL @ 2024-03-14 13:14:33
@[monkeyinGD](/user/982629) 原来是这样,,感谢感谢
by o_CIHL @ 2024-03-14 13:15:10
@[o_CIHL](/user/1165228) 能问一下贴主怎么改的吗,bfs应该没有问题但是我用bfs同样MLE了,仅12分其他全MLE,代码如下应该没有问题:
```cpp
#include <bits/stdc++.h>
using namespace std;
int mp[205];
int n,a,b,cnt,ans = INT_MAX;
bool flag;
void dfs(int now)
{
if(now == b)
{
flag = true;
ans = min(ans,cnt);
return;
}
for(int i = 1,sta = 1; i <= 2; i++,sta *= -1)
{
int next = now + mp[now] * sta;
if(next >= 1 && next <= n)
{
cnt++;
dfs(next);
cnt--;
}
}
}
int main()
{
cin>>n>>a>>b;
for(int i = 1; i <= n; i++) cin>>mp[i];
dfs(a);
if(flag) cout<<ans;
else cout<<"-1";
return 0;
}
```
by liwenliwenllll @ 2024-03-24 01:52:18
@[liwenliwenllll](/user/1186230) 打错字了我用的是dfs
by liwenliwenllll @ 2024-03-24 01:53:08
@[liwenliwenllll](/user/1186230)
这个题目我到最后就过了两个数据,36分。
目前dfs 还不是很熟练,做一做其他的dfs之后看看能不能过。
也有可能这个题目dfs就是不能过全部的数据,必须用其他的算法,,也是有这种可能的。
by o_CIHL @ 2024-03-25 20:27:02
@[o_CIHL](/user/1165228) 后来我用dfs剪枝后AC了。就是:遍历到next电梯的时候,如果当前电梯的cnt比next电梯的cnt大(用了cnt[]记录),就剪枝,因为当前已经不可能成为答案了。bfs很好ac
by liwenliwenllll @ 2024-03-26 22:46:54
@[liwenliwenllll](/user/1186230) 好的好的,,感谢捏
by o_CIHL @ 2024-03-28 15:33:47