Submission #937681

#	Time	Username	Problem	Language	Result	Execution time	Memory
937681		zwezdinv	Maze (JOI23_ho_t3)	C++17	100 / 100	1263 ms	501612 KiB

Main

#include <bits/stdc++.h>

struct node {
        int x, y, free, dist;
        node() = default;
        node(int x, int y, int free, int dist) : x(x), y(y), free(free), dist(dist) {}
};

std::vector<std::pair<int, int>> dir1 = {
        {0, 1},
        {0, -1},
        {1, 0},
        {-1, 0}
};
std::vector<std::pair<int, int>> dir2 = {
        {1, 1},
        {1, -1},
        {-1, 1},
        {-1, -1}
};

int main() {
        std::cin.tie(nullptr)->sync_with_stdio(false);

        int r, c, n;
        std::cin >> r >> c >> n;
        int sx, sy, fx, fy;
        std::cin >> sx >> sy >> fx >> fy;
        --sx, --sy, --fx, --fy;
        std::vector a(r, std::vector(c, '#'));
        for (auto& i : a) {
                for (auto& j : i) {
                        std::cin >> j;
                }
        }
        std::queue<node> cur, nxt;
        std::vector used(r, std::vector(c, false));
        cur.emplace(sx, sy, 0, 0);
        while (cur.size() || nxt.size()) {
                if (cur.empty()) std::swap(cur, nxt);
                node u = cur.front();
                cur.pop();
                if (u.x == fx && u.y == fy) {
                        std::cout << u.dist << '\n';
                        break;
                }
                if (used[u.x][u.y]) continue;
                used[u.x][u.y] = true;
                for (auto [dx, dy] : dir1) {
                        int i = u.x + dx, j = u.y + dy;
                        if (i < 0 || i >= r || j < 0 || j >= c) continue;
                        if (a[i][j] == '.') {
                                cur.emplace(i, j, std::max(u.free - 1, 0), u.dist);
                        }
                        if (u.free == 0) {
                                nxt.emplace(i, j, n - 1, u.dist + 1);
                        } else {
                                cur.emplace(i, j, u.free - 1, u.dist);
                        }
                }
                for (auto [dx, dy] : dir2) {
                        int i = u.x + dx, j = u.y + dy;
                        if (i < 0 || i >= r || j < 0 || j >= c) continue;
                        if (u.free >= 2) {
                                cur.emplace(i, j, u.free - 1, u.dist);
                        } else if (n >= 2) {
                                nxt.emplace(i, j, n - 1, u.dist + 1);
                        }
                }
        }
}

• Subtask 1: 8 / 8
• Subtask 2: 19 / 19
• Subtask 3: 16 / 16
• Subtask 4: 19 / 19
• Subtask 5: 5 / 5
• Subtask 6: 19 / 19
• Subtask 7: 8 / 8
• Subtask 8: 6 / 6