P1135 奇怪的电梯 （6）
zhouwc
2018-02-25 09:18:54
这道题，我再我自己的oj上错了6次才过（不敢在洛谷上刷低通过率）。。。本来想用dfs的，后面想了想还是bfs好用。
主要错误原因：
- 我忘记了会陷入死循环的情况，所以应该要向dfs一样，走过的点应该要进行标记，不然可以一直再走。导致答案错误。应该也算是剪枝吧。
- 粗心的我忽略了一种情况。当一开始x==y的时候应该要特判。而我再修改了第一种错误之后忘记了第二种错误。所以又错了一个点。
下面，贴一个代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
int f[1000005],b[1000005],a[205],n,x,y;
bool c[1000005];
int main()
{
scanf("%d%d%d",&n,&x,&y);
for (int i=1;i<=n;i++)
scanf("%d",&a[i]);
if (x==y)
{
printf("0");
return 0;
}
int head=0; int tail=1;
f[tail]=x; b[tail]=0;
c[x]=true;
while (head<=tail)
{
head++;
if (f[head]+a[f[head]]<=n)
if (c[f[head]+a[f[head]]]==false)
{
tail++;
f[tail]=f[head]+a[f[head]];
b[tail]=b[head]+1;
c[f[head]+a[f[head]]]=true;
if (f[head]+a[f[head]]==y)
{
printf("%d",b[tail]);
return 0;
}
}
if (f[head]-a[f[head]]>=1&&c[f[head]-a[f[head]]]==false)
{
tail++;
f[tail]=f[head]-a[f[head]];
b[tail]=b[head]+1;
c[f[head]-a[f[head]]]=true;
if (f[tail]==y)
{
printf("%d",b[tail]);
return 0;
}
}
}
printf("-1");
}
```
自己需要好好反思一下