Submission #1045509

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045509		juicy	Maze (JOI23_ho_t3)	C++17	100 / 100	291 ms	69396 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);

    const int dx[] = {-1, 0, 1, 0};
    const int dy[] = {0, 1, 0, -1};

    int n, m, k; cin >> n >> m >> k; --k;
    int r, c, s, t; cin >> r >> c >> s >> t;
    vector<string> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    auto bfs = [&](int sr, int sc, int tr, int tc) {
        queue<array<int, 2>> W;
        queue<array<int, 4>> B;
        vector d(n, vector<int>(m, -1));
        auto inside = [&](int i, int j) {
            return 0 <= i && i < n && 0 <= j && j < m && d[i][j] == -1;
        };
        d[sr][sc] = 0;
        W.push({sr, sc});
        while (W.size() || B.size()) {
            while (W.size()) {
                auto [u, v] = W.front(); W.pop();
                for (int dr = 0; dr < 4; ++dr) {
                    int x = u + dx[dr], y = v + dy[dr];
                    if (inside(x, y)) {
                        if (a[x][y] == '.') {
                            d[x][y] = d[u][v];
                            W.push({x, y});
                        } else {
                            d[x][y] = d[u][v] + 1;
                            B.push({x, y, k, k});
                        }
                    }
                }
            }
            while (B.size()) {
                auto [u, v, a, b] = B.front(); B.pop();
                if (a == 0 || b == 0) {
                    W.push({u, v});
                }
                for (int dr = 0; dr < 4; ++dr) {
                    int x = u + dx[dr], y = v + dy[dr], i = a - abs(dx[dr]), j = b - abs(dy[dr]);
                    if (i >= 0 && j >= 0 && inside(x, y)) {
                        d[x][y] = d[u][v];
                        B.push({x, y, i, j});
                    }
                }
            }
        }
        return d[tr][tc];
    };
    cout << bfs(r - 1, c - 1, s - 1, t - 1);
    return 0;
}

• 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