dfs52分求助,#1~5WA#6 14 15TLE
查看原帖
dfs52分求助,#1~5WA#6 14 15TLE
1469998
wayne_15532楼主2024/10/27 13:36
#include <iostream>
#include <climits>
using namespace std;

const int maxn = 210;

int N, A, B, nfloor[maxn], ans = INT_MAX;
bool check[maxn];

void dfs(int state, int times) {
	if (state < 0 || state > N)
		return;

	if (state == B) { 
		ans = min(ans, times);
		return;
	}

	if (state + nfloor[state] <= B && !check[state + nfloor[state]]){
		check[state + nfloor[state]] = true;
		dfs(state + nfloor[state], times + 1);
		check[state + nfloor[state]] = false;
	}

	if (state - nfloor[state] > 0 && !check[state - nfloor[state]]) {
		check[state - nfloor[state]] = true;
		dfs(state - nfloor[state], times + 1);
		check[state - nfloor[state]] = false;
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> N >> A >> B;
	for (int i = 1;i <= N; ++i)
		cin >> nfloor[i];
	dfs(A, 0);
	if (ans == INT_MAX) {
		cout << -1;return 0;
	}
	cout << ans;
	return 0;
}
2024/10/27 13:36
加载中...