QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#560667 | #9224. Express Eviction | ucup-team3519# | WA | 1ms | 3748kb | C++20 | 2.9kb | 2024-09-12 17:15:45 | 2024-09-12 17:15:46 |
Judging History
answer
#include <bits/stdc++.h>
constexpr int INF = 1e9;
int bellman_ford(const std::vector<std::pair<std::pair<int, int>, int>> &edges, int s, int t) {
int n = 0;
for (auto [p, w] : edges) {
n = std::max({n, p.first + 1, p.second + 1});
}
std::vector<int> dist(n, INF);
dist[s] = 0;
for (int i = 0; i < edges.size(); ++i) {
bool flag = false;
for (auto [p, w] : edges) {
auto [u, v] = p;
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
flag = true;
}
}
if (!flag) {
break;
}
}
return dist[t];
}
void solve() {
int h, w;
std::cin >> h >> w;
std::vector<std::string> arr(h);
for (int i = 0; i < h; ++i) {
std::cin >> arr[i];
}
auto check_X = [&](int x, int y) -> bool {
return x >= 0 && x <= h && y >= 0 && y <= w;
};
auto f = [&](int x, int y) -> int {
if (x < 0 || x >= h || y < 0 || y >= w) {
return 0;
}
return arr[x][y] == '#';
};
constexpr int I = 0, O = 1;
std::vector<std::pair<std::pair<int, int>, int>> edges;
auto add_edge = [&](int u, int v, int w) {
edges.emplace_back(std::make_pair(u, v), w);
};
/**
* .0.
* 1#2
* .3.
*/
auto get = [&](int x, int y, int t, int io) {
return (x * (w + 1) + y) * 8 + t * 2 + io;
};
for (int x = 0; x <= h; ++x) {
for (int y = 0; y <= w; ++y) {
auto add_link = [&](int u, int v, int w) {
add_edge(get(x, y, u, I), get(x, y, v, O), w);
add_edge(get(x, y, v, I), get(x, y, u, O), w);
};
// 02
add_link(0, 2, f(x - 1, y - 1) - f(x, y));
// 23
add_link(2, 3, f(x - 1, y) - f(x, y - 1));
// 31
add_link(3, 1, f(x, y) - f(x - 1, y - 1));
// 10
add_link(1, 0, f(x, y - 1) - f(x - 1, y));
// 03 12
add_link(0, 3, 0);
add_link(1, 2, 0);
if (check_X(x, y + 1)) {
add_edge(get(x, y, 0, O), get(x, y + 1, 3, I), f(x - 1, y) + f(x, y));
}
if (check_X(x - 1, y)) {
add_edge(get(x, y, 1, O), get(x - 1, y, 2, I), f(x - 1, y) + f(x - 1, y - 1));
}
if (check_X(x + 1, y)) {
add_edge(get(x, y, 2, O), get(x + 1, y, 1, I), f(x, y) + f(x, y - 1));
}
if (check_X(x, y - 1)) {
add_edge(get(x, y, 3, O), get(x, y - 1, 0, I), f(x - 1, y - 1) + f(x, y - 1));
}
}
}
std::cout << bellman_ford(edges, get(0, 0, 0, I), get(h, w, 2, O)) << '\n';
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
solve();
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3624kb
input:
4 6 .##... .#.... ##.... ....#.
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 3748kb
input:
20 30 ...########################### #..########################### ...########################### ...########################### .############################# ...########################### ...########################### #..########################### ...########################### ..#...............
output:
13
result:
wrong answer 1st numbers differ - expected: '11', found: '13'