关于回溯搜索这件事...
查看原帖
关于回溯搜索这件事...
668866
Dream_and_FACT楼主2022/7/1 21:23

回溯不是跑很慢的吗,那个大佬帮蒟蒻解释一下... 61ms...

#include <iostream>
using namespace std;
int n,x,y,floor[205];
bool vis[205];
int ans=1e9;
bool check(int x){
	if(x<1||x>n||vis[x])return false;
	return true;
}
void dfs(int x,int y,int sum){
	if(x==y){
		ans=min(ans,sum);
		return ;
	}
	if(sum>ans){
		return ;
	}
	vis[x]=true;
	if(check(x+floor[x])) dfs(x+floor[x],y,sum+1);
	if(check(x-floor[x])) dfs(x-floor[x],y,sum+1);
	vis[x]=false;
} 
int main(){
	cin>>n>>x>>y;
	for(int i=1;i<=n;i++)cin>>floor[i];
	dfs(x,y,0);
	if(ans==1e9)cout<<-1<<endl;
	else cout<<ans<<endl;
	return 0;
}
2022/7/1 21:23
加载中...