DFS #4 #9 # 10 WA 求助
查看原帖
DFS #4 #9 # 10 WA 求助
1023060
Stefan_Zhao楼主2023/6/27 22:28
#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int MAXN = 300;

int A, B, N;
int K[MAXN];
int x;//记录当前在第几楼
int arr[MAXN];//记录每一步在哪一楼用array方便回溯
bool st[MAXN];//MLE了,应该是要不能走“回头路”?
int res = 1e9;
int ct = 0;

void dfs(int x)
{
    if(st[x]) return ;
    if(x < 1 || x > N) return ;//剪枝
    if(x == B){
        if(ct < res){
            res = ct;
        }
        return ;
    }
    
    arr[ct] = K[x];//记录一下这一步是跳到哪里
    st[x] = true;//这里不要再走
    x += K[x];//到下一个位置
    ct ++;//计数增加
    dfs(x);
    x -= arr[ct];//不是x -= K[x];,因为非法而退出这个时候你的K[x]=0!
    st[x] = false;
    ct --;
    
    arr[ct] = K[x];
    st[x] = true;
    x -= K[x];
    ct ++;
    dfs(x);
    x += arr[ct];
    st[x] = false;
    ct --;
}

int main()
{
    scanf("%d %d %d", &N, &A, &B);
    for(int i= 1; i <= N; i++){
        scanf("%d", &K[i]);
    }
    dfs(A);
    if(res < 1e9) printf("%d\n", res);
    else printf("%d\n", -1);
    return 0;
}
2023/6/27 22:28
加载中...