42分求助 QwQ
查看原帖
42分求助 QwQ
1245542
like_1999楼主2024/8/11 16:33
# include<bits/stdc++.h>
using namespace std;
int N , A , B , c , record_1 , d , e , K[2000] , record[20000] , temp[2000] , temp1[2000];
void DFS (int record_2 , int A_1) {
	if (A_1 == B) {
		record[c] = record_2;
		c++;
		e = 1;
	}
	else {
		if (A_1 != B && K[A_1] == 0) {
			return;
		}		
		if (A_1 - K[A_1] > 0 && temp[K[A_1] + A_1] == 0) {
			temp[A_1 - K[A_1]] = 1;
			DFS(record_2 + 1 , A_1 - K[A_1]);
			temp[A_1 - K[A_1]] = 0;
		}
		if (K[A_1] + A_1 <= N && temp[K[A_1] + A_1] == 0) {
			temp[K[A_1] + A_1] = 1;
			DFS(record_2 + 1 , A_1 + K[A_1]);
		}
	}
}
int main() {
 	cin >> N >> A >> B;
 	for (int i = 1 ; i <= N ; i++) {
 		cin >> K[i];
	}
	temp[A] = 1;
	DFS(record_1 , A);
	if (e == 0) {
		cout << "-1";
		return 0;
	}
	d = record[0];
	for (int q = 0 ; q < c ; q++) {
		if (d > record[q]) d = record[q];
	}
	cout << d;
    return 0;
}
2024/8/11 16:33
加载中...