dfs卡#1,求优化剪枝
查看原帖
dfs卡#1,求优化剪枝
877691
MorLeaves楼主2023/8/4 12:59
#include<iostream>
#include<cstdio>
using namespace std;
int n,a,b,k[114514],ans=233114514;
bool bo[114514]={};
void dfs(int x,int s)
{
	if (x==b)
	{
		ans=s<ans?s:ans;
	}
	if (s>ans)
	{
		return ;
	}
	bo[x]=true;
	if (x+k[x]<=n&&bo[x+k[x]]==false)
	{
		dfs(x+k[x],s+1);
	}
	if (x-k[x]>=1&&bo[x-k[x]]==false)
	{
		dfs(x-k[x],s+1);
	}
	bo[x]=false;
}
int main()
{
	scanf("%d %d %d",&n,&a,&b);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&k[i]);
	}
	bo[a]=1;
	dfs(a,0);
	printf("%d",ans==233114514?-1:ans);
	return 0;
}
2023/8/4 12:59
加载中...