QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#560667#9224. Express Evictionucup-team3519#WA 1ms3748kbC++202.9kb2024-09-12 17:15:452024-09-12 17:15:46

Judging History

你现在查看的是最新测评结果

  • [2024-09-12 17:15:46]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3748kb
  • [2024-09-12 17:15:45]
  • 提交

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'