社区讨论

24分RE代码求调

P1135奇怪的电梯参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@lzl7mskx
此快照首次捕获于
2024/08/08 19:43
2 年前
此快照最后确认于
2024/08/08 19:43
2 年前
查看原帖
CPP
#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代码求调~
CPP
#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;
}

回复

0 条回复,欢迎继续交流。

正在加载回复...