除了第一点过不去,其他的没问题,但是我有一些除此之外的疑惑
查看原帖
除了第一点过不去,其他的没问题,但是我有一些除此之外的疑惑
493163
希赟xiyun楼主2023/4/1 00:21
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int N,A,B;
int k[205];
bool a[205];
int m=1e9;
void dfs(int x,int ans)
{
    if(ans>=m)   return;
    if(x==B)
    {
        m=min(ans,m);
        return;
    }
    //上
    if(x+k[x]<=N&&!a[x+k[x]]&&k[(x+k[x])]!=0)
    {
        a[x+k[x]]=true;
        dfs(x+k[x],ans+1);
        a[x+k[x]]=false;
    }
    //下
    if(x-k[x]>0&&!a[x-k[x]]&&k[(x-k[x])]!=0)
    {
        a[x-k[x]]=true;
        dfs(x-k[x],ans+1);
        a[x-k[x]]=false;
    }
}
int main()
{
    scanf("%d %d %d",&N,&A,&B);
    for(int i=1;i<=N;i++)
    {
        scanf("%d",&k[i]);
    }
    dfs(A,0);
    if(m==1e9)
    {
        printf("-1");
        return 0;
    }
    printf("%d",m);
    return 0;
}

我注意到题目里,楼层Ki可能等于0,所以我在if的判断里对下一楼层是否为0进行判断,虽然不判断引入bool数组后(保证每层楼只走一次 剪枝)程序是一样进行的,但是我对下一楼层进行非0判断后, #9#10测试点TLE, #4#6#7#11测试点直接WA了,不引入判断的话,除了第一个TLE其他的去全部通过

2023/4/1 00:21
加载中...