제출 #515617

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
515617		KoD	Patkice II (COCI21_patkice2)	C++17	110 / 110	263 ms	40900 KiB

Main

#include <bits/stdc++.h>

using std::vector;
using std::array;
using std::pair;
using std::tuple;

constexpr int inf = std::numeric_limits<int>::max() / 2;

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int H, W;
    std::cin >> H >> W;
    vector<char> grid(H * W);
    for (auto& x : grid) {
        std::cin >> x;
    }
    int src = 0, dst = 0;
    while (grid[src] != 'o') src += 1;
    while (grid[dst] != 'x') dst += 1;
    vector<int> dist(H * W, inf), parent(H * W, -1);
    dist[src] = 0;
    std::deque<int> que = {src};
    while (!que.empty()) {
        const int u = que.front();
        que.pop_front();
        const int i = u / W, j = u % W;
        const auto push0 = [&](const int v) {
            if (dist[v] > dist[u]) {
                dist[v] = dist[u];
                parent[v] = u;
                que.push_front(v);
            }
        };
        const auto push1 = [&](const int v) {
            if (dist[v] > dist[u] + 1) {
                dist[v] = dist[u] + 1;
                parent[v] = u;
                que.push_back(v);
            }
        };
        if (grid[u] == '<' and j > 0) push0(u - 1);
        if (grid[u] == '>' and j + 1 < W) push0(u + 1);
        if (grid[u] == '^' and i > 0) push0(u - W);
        if (grid[u] == 'v' and i + 1 < H) push0(u + W);
        if (j > 0) push1(u - 1);
        if (j + 1 < W) push1(u + 1);
        if (i > 0) push1(u - W);
        if (i + 1 < H) push1(u + W);
    }
    std::cout << dist[dst] - 1 << '\n';
    while (parent[dst] != src) {
        const int prv = parent[dst];
        if (prv - 1 == dst) grid[prv] = '<';
        if (prv + 1 == dst) grid[prv] = '>';
        if (prv - W == dst) grid[prv] = '^';
        if (prv + W == dst) grid[prv] = 'v';
        dst = prv;
    }
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            std::cout << grid[i * W + j];
        }
        std::cout << '\n';
    }
    return 0;
}

• Subtask 1: 30 / 30
• Subtask 2: 80 / 80