QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#648270 | #7781. Sheep Eat Wolves | enar# | RE | 0ms | 0kb | C++20 | 1.5kb | 2024-10-17 18:02:32 | 2024-10-17 18:02:32 |
answer
#include <bits/stdc++.h>
using i64 = long long;
const int INF = 1E9;
struct Node {
int cnt, sp, wv;
};
void solve() {
int x, y, p, q;
std::cin >> x >> y >> p >> q;
std::queue<Node> pq;
std::vector vis(2, std::vector(101, std::vector<bool>(101)));
int ans = INF;
pq.push({0, 0, 0});
while (!pq.empty()) {
auto [c, a, b] = pq.front();
pq.pop();
vis[c % 2][a][b] = 1;
if (a == x) {
ans = std::min(ans, c);
break;
}
if (c % 2 == 0) {
for (int i = 0; i <= x - a && i <= p; ++i) {
for (int j = (a + i == x ? 0 : y - b - x + a + i - q); j <= y - b && j <= p - i; ++j) {
if (vis[(c + 1) % 2][a + i][b + j]) continue;
pq.push({c + 1, a + i, b + j});
vis[(c + 1) % 2][a + i][b + j] = 1;
}
}
} else {
for (int i = 0; i <= a && i <= p; ++i) {
for (int j = (a == i ? 0 : b - a + i - q); j <= b && j <= p - i; ++j) {
if (vis[(c + 1) % 2][a - i][b - j]) continue;
pq.push({c + 1, a - i, b - j});
vis[(c + 1) % 2][a - i][b - j] = 1;
}
}
}
}
if (ans == INF) ans = -1;
std::cout << ans << "\n";
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T = 1;
// std::cin >> T;
while(T--) {
solve();
}
}
详细
Test #1:
score: 0
Runtime Error
input:
4 4 3 1