社区讨论
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 条回复,欢迎继续交流。
正在加载回复...