洛谷P1135奇怪的电梯

bad_404 · 2018-06-03 22:17:16 · 题解

我用的DFS，没时间解释了，上车再说

#include<bits/stdc++.h>
using namespace std;
int n,start,last,a[210],book[210],minest=99999;
void dfs(int x,int step)
{
    int x1=x-a[x],x2=x+a[x];
    if(x<=0||x>200) return ;//保证是在范围内
    if(x==last)//找到终点就找小值
    {
        if(step<minest) 
            minest=step;
        return ;
    }
    else if(step<=minest)//如果当前步数已经超过了目前的最小值，就一定不为最优解
    {
        if(book[x1]==0)
        {
            book[x1]=1;
            dfs(x1,step+1);
            book[x1]=0;
        }
        if(book[x2]==0)
        {
            book[x2]=1;
            dfs(x2,step+1);
            book[x2]=0;
        }
        return ;
    }
}
int main()
{
    int i;
    scanf("%d%d%d",&n,&start,&last);//输入楼层总数，A，B楼
    if(start==last) {printf("0"); return 0;}
    for(i=1;i<=n;i++)
    scanf("%d",&a[i]);//Ki
    dfs(start,0);//从起点深搜
    if(minest==99999) {printf("-1"); return 0;}
    printf("%d",minest);
    return 0;
}