24分RE代码求调
查看原帖
24分RE代码求调
1014640
封禁用户楼主2024/8/8 19:42
#include <iostream>
#include <cstdio>
#define int long long

using namespace std;
const int N = 255;
int k[N];

struct Node {
	int w, nxt, afte;
	int step;
} s[N * N * 20];

signed main() {
	int n, a, b;
	cin >> n >> a >> b;
	for (int i = 1; i <= n; ++i) 
		cin >> k[i];
	int head, tail;
	head = 1, tail = 1;
	s[head].step = 0;
	s[head].w = a;
	s[head].nxt = k[a];
	s[head].afte = 0;
	while (s[head].w != b) {
		if (s[head].step > n * n)
			break;
		if (s[head].w - s[head].nxt >= 1 && s[head].w - s[head].nxt != s[head].afte) {
			tail++;
			s[tail].w = s[head].w - s[head].nxt;
			s[tail].nxt = k[s[tail].w];
			s[tail].afte = s[head].w;
			s[tail].step = s[head].step + 1;
			if (s[tail].w == b) {
				cout << s[tail].step;
				return 0;
			}
		}
		if (s[head].w + s[head].nxt <= n && s[head].w + s[head].nxt != s[head].afte) {
			tail++;
			s[tail].w = s[head].w + s[head].nxt;
			s[tail].nxt = k[s[head].w + s[head].nxt];
			s[tail].afte = s[head].w;
			s[tail].step = s[head].step + 1;
			if (s[tail].w == b) {
				cout << s[tail].step;
				return 0;
			}
		}
		head++;
	}
	cout << -1;
	return 0;
} 

另外附上30分dfs代码求调~

#include <iostream>
#include <cstdio>

using namespace std;
const int N = 245;
int k[N], index, cnt = -1, ans = N;
int n, a, b, lastLine = 0;

void dfs(int b) {
	if (index == b) {
		ans = min(ans, cnt);
		return;
	}
	cnt++;
	if (cnt >= ans) return;
	if (index - k[index] >= 1 && lastLine != index - k[index]) {
		int tmp = index;
		lastLine = index;
		index -= k[index];
		dfs(b);
		index += k[index];
		lastLine = tmp;
		cnt--;
	}
	if (index + k[index] <= n && lastLine != index + k[index]) {
		int tmp = index;
		lastLine = index;
		index += k[index];
		dfs(b);
		index -= k[index];
		lastLine = tmp;
		cnt--;
	}
}

int main() {
	cin >> n >> a >> b;
	for (int i = 1; i <= n; ++i)
		cin >> k[i];
	index = a;
	dfs(b);
//	if (cnt == 0) 
//		cout << -1;
	cout << ans;
	return 0;
}
2024/8/8 19:42
加载中...