一道dfs题,救救孩子吧,真不知道问题在哪
查看原帖
一道dfs题,救救孩子吧,真不知道问题在哪
1150009
cz_Huang楼主2024/3/12 23:24
#include<bits/stdc++.h> 
using namespace std;
int n,a,b,k[205],kp[205]; //minsum记录当前为止最少的步数 kp来记录每一层是否到达过 
long long minsum=11451400;
void dfs(long long sum,long long p) //sum为当前的步数,p为当前的位置 
{
	if(p==b) 
	{
		minsum=sum;
		return;
	}
	if(p<1||p>n||sum==minsum||kp[p]==1) return;
	kp[p]=1; //记录这一层已经到达过 
	dfs(sum+1,p+k[p]);
	dfs(sum+1,p-k[p]);
}
int main (void)
{
	cin>>n>>a>>b;
	for(int i=1;i<=n;i++) cin>>k[i];
	dfs(0,a);
	if(minsum==11451400) cout<<-1;
	else cout<<minsum;
	return 0;
} 
 
2024/3/12 23:24
加载中...