dfs,#10TLE求助
查看原帖
dfs,#10TLE求助
1041187
mutianhanhan楼主2023/10/4 11:53
#include <bits/stdc++.h>
using namespace std;
int N, A, B;
int a[201];
bool b[201];
int ans = 0;//得到答案前计数用的
int print;//应该输出的答案
bool check = 0;

void dfs(int now, int to) {
	b[now] = 1;

	if (now == to) {
		check = 1;
		print = ans;
		return ;
	}

	if (now >= to) {
		if (now - a[now] >= 1 && b[now - a[now]] == 0) {
			ans++;
			if ((b[now + a[now]] == 1 || now + a[now] > N) && (b[now - a[now]] == 1 || now - a[now] < 1)) {
				return ;
			} else
				dfs(now - a[now], to);
		}

		if (now + a[now] <= N && b[now + a[now]] == 0) {
			ans++;

			if ((b[now + a[now]] == 1 || now + a[now] > N) && (b[now - a[now]] == 1 || now - a[now] < 1)) {
				return ;
			} else
				dfs(now + a[now], to);
		}
	} else if (to >= now) {
		if (now + a[now] <= N && b[now + a[now]] == 0) {
			ans++;

			if ((b[now + a[now]] == 1 || now + a[now] > N) && (b[now - a[now]] == 1 || now - a[now] < 1)) {
				return ;
			} else
				dfs(now + a[now], to);

			if (now - a[now] >= 1 && b[now - a[now]] == 0) {
				ans++;

				if ((b[now + a[now]] == 1 || now + a[now] > N) && (b[now - a[now]] == 1 || now - a[now] < 1)) {
					return ;
				} else
					dfs(now - a[now], to);
			}
		}

		ans--;
		b[now] = 0;

	}
}

	int main() 
	{
		memset(b, 0, sizeof(b));
		cin >> N >> A >> B;
		b[A] = 1;

		for (int i = 1; i <= N; i++)

			cin >> a[i];
		dfs(A, B);

		if (check == 1)
			cout << print;

		if (check == 0)
			cout << "-1";

		return 0;

	}
2023/10/4 11:53
加载中...