POJ1135 奇怪的电梯 DFS深搜

原题链接： https://www.luogu.com.cn/problem/P1135

考虑用dfs来做的话，单纯的深搜会超时，而且不一定搜出来的就是最小的(bfs: ?)
我们需要一边判断当前搜到的按按钮数，取最小的存下来，同时存下状态进行记忆化搜索。

#include <iostream>
using namespace std;

const int N = 220;
int p[N];
int n,x,y;
int ox[] = {1,-1};
int count = 1e5;

int dst[N];

void dfs(int x,int y,int u){
    //当按按钮的次数已超过上次取的最小值，进行剪枝
    if(u>count) return;
    //走到目的地了，判断上次存下来的次数，取min
    if(x==y){
    	count = u<count?u:count;
    	return;
    }
   //每次回溯前的搜索，每个点都只能被走一次
    dst[x] = 1;
   //往深处搜
    for(int i=0;i<2;i++){
    	int nx = x+(ox[i]*p[x]);
        //判断边界
    	if(nx>=1&&nx<=y&&nx!=x&&!dst[nx]){
    		dfs(nx,y,u+1);
                //回溯(回到这里的时候,nx会被标记为不可用,为了让i接着走,需要恢复现场)
    		dst[nx]=0;
	}
    } 
}


int main(){
    cin>>n>>x>>y;
    for(int i=1;i<=n;i++) cin>>p[i];
    dfs(x,y,0);
    cout << (count==1e5?-1:count) << endl;
    return 0;
}

当然，并不是一帆风顺…