64分dfs做法
查看原帖
64分dfs做法
977431
maoyuqi楼主2024/1/18 18:31
#include<bits/stdc++.h>
using namespace std;
int k[300],book[300];
int n,a,b;
int ans = 100000;
void dfs(int floor,int step)
{
	if(floor==b)
	{
		ans=min(ans,step);
		return;
	}
	if(step>ans) return;
	int v = floor-k[floor];
	int v2 = floor+k[floor];
	if(v>=1&&book[v]==0)
	{
		book[v]=1;
		dfs(v,step+1);
		book[v]=0;
	}
	if(v2<=n&&book[v2]==0)
	{
		book[v2]=1;
		dfs(v2,step+1);
		book[v2]=0;
	}
	return;
}
int main()
{
	cin>>n>>a>>b;
	for(int i = 1;i<=n;i++) cin>>k[i];
	book[a]=1;
	dfs(a,0);
	if(ans==100000) cout<<-1<<endl;
	else cout<<ans<<endl;
	return 0;
}
2024/1/18 18:31
加载中...