80分,#8#9出错(WA)
查看原帖
80分,#8#9出错(WA)
557887
acahv楼主2022/2/15 21:08

都说#8#9wa是回溯问题,但是我回溯了呀qaq

检查了一小时都没有查出错在哪

#include<bits/stdc++.h>
using namespace std;

int N,A,B;
int a[400];
bool vis[400];

int cnt=114514;
void dfs(int c,int now)
{
	if(now==B)
	{
		if(c<=cnt)
			cnt=c;
		return;
	}
	if(now>=cnt)
		return;
	if(vis[now+a[now]]==0 && now+a[now]<=B)
	{
		vis[now]=1;
		dfs(c+1,now+a[now]);
		vis[now]=0;
	}
	if(vis[now-a[now]]==0 && now-a[now]>=1)
	{
		vis[now]=1;
		dfs(c+1,now-a[now]);
		vis[now]=0;
	}
}

int main()
{
	cin>>N>>A>>B;
	for(int i=1;i<=N;i++)
	{
		cin>>a[i];
	}
	vis[A]=1;
	dfs(0,A);
	if(cnt!=114514)
	{
		cout<<cnt;
	}
	else if(cnt==114514)
	{
		cout<<-1;
	}
	return 0;
}
2022/2/15 21:08
加载中...