请问为什么#9#10不过?用的是深度优先搜索
查看原帖
请问为什么#9#10不过?用的是深度优先搜索
374722
gongchuqiao楼主2021/12/15 21:52
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
using namespace std;

const int INF = 2147483647;
const int MAXN = 2e2 + 50;

int k[MAXN];
bool vis[MAXN];

int n;
int a, b;
int ans = INF;

void dfs(int now, int d)
{
//	printf("depth:%d,now:%d,will goto:%d\n", d, now, k[now]);
	vis[now] = true;
	if (now == b)
	{
		ans = min(ans, d);
		return ;
	}
	for (int i = 0;i <= 1;i++)
	{
		int next;
		if (i == 1)
			next = now - k[now];
		else
			next = now + k[now];
		if (next < 1 || n < next)
			continue;
		if (vis[next])
			continue;
		dfs(next, d + 1);
	}
}

int main()
{
	scanf("%d %d %d", &n, &a, &b);
	for (int i = 1;i <= n;i++)
		scanf(" %d", &k[i]);
	if (a == b)
	{
		printf("0");
		return 0;
	}
	dfs(a,0);
	if (ans == INF)
	{
		printf("-1");
		return 0;
	}
	printf("%d", ans);
	return 0;
}
2021/12/15 21:52
加载中...