Submission #895941

#	Time	Username	Problem	Language	Result	Execution time	Memory
895941		frostray8653	Maze (JOI23_ho_t3)	C++17	67 / 100	2015 ms	65608 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
using pii = pair<int, int>;
#define IO ios::sync_with_stdio(0), cin.tie(0)
#define FOR(p, a, b) for (int p = a; p <= b; p++)
void dbg() {;}
template<class T, class ...U>
void dbg(T a, U ...b) {cout << a << (sizeof...(b) ? ", " : " "); dbg(b...);}
void ent() {cout << "\n";}
/// ---- INITIAL END ----

const int INF = 1e15;
const int N = 200005;

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

signed main() {
    IO;
    // freopen("out.txt", "w", stdout);
    
    int r, c, n;
    cin >> r >> c >> n;
    int sx, sy, tx, ty;
    cin >> sx >> sy >> tx >> ty;
    sx -= 1; sy -= 1; tx -= 1; ty -= 1;
    vector<string> v(r);
    FOR (i, 0, r - 1) cin >> v[i];

    auto inside = [&](int x, int y) {
        return (0 <= x && x < r && 0 <= y && y < c);
    };

    vector<vector<int>> dis(r, vector<int>(c, INF));
    priority_queue<pair<int, pii>, vector<pair<int, pii>>, greater<pair<int, pii>>> Q;
    Q.push({0, {sx, sy}});
    dis[sx][sy] = 0;
    int ans = INF;
    while (! Q.empty()) {
        int step = Q.top().first;
        pii pos = Q.top().second;
        auto [x, y] = pos;
        Q.pop();
        if (ans != INF && step >= ans) {
            cout << ans << "\n";
            return 0;
        }

        if (step != dis[x][y]) continue;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (inside(nx, ny) && v[nx][ny] == '.') {
                if (step < dis[nx][ny]) {
                    if (nx == tx && ny == ty) {
                        cout << step << "\n";
                        return 0;
                    }
                    dis[nx][ny] = step;
                    Q.push({dis[nx][ny], {nx, ny}});
                }
            }
        }
        if (x - n <= tx && tx <= x + n && y - n <= ty && ty <= y + n) {
            ans = min(ans, step + 1);
            continue;
        }
        int L = max(0ll, x - n), R = min(r - 1, x + n);
        int D = max(0ll, y - n), U = min(c - 1, y + n);
        for (int nx = L, ny = D; ny <= U; ny++) {
            if (abs(nx - x) + abs(ny - y) == 2 * n) continue;
            if (step + 1 < dis[nx][ny]) {
                dis[nx][ny] = step + 1;
                Q.push({dis[nx][ny], {nx, ny}});
            }
        }
        for (int nx = R, ny = D; ny <= U; ny++) {
            if (abs(nx - x) + abs(ny - y) == 2 * n) continue;
            if (step + 1 < dis[nx][ny]) {
                dis[nx][ny] = step + 1;
                Q.push({dis[nx][ny], {nx, ny}});
            }
        }
        for (int nx = L, ny = U; nx <= R; nx++) {
            if (abs(nx - x) + abs(ny - y) == 2 * n) continue;
            if (step + 1 < dis[nx][ny]) {
                dis[nx][ny] = step + 1;
                Q.push({dis[nx][ny], {nx, ny}});
            }
        }
        for (int nx = L, ny = D; nx <= R; nx++) {
            if (abs(nx - x) + abs(ny - y) == 2 * n) continue;
            if (step + 1 < dis[nx][ny]) {
                dis[nx][ny] = step + 1;
                Q.push({dis[nx][ny], {nx, ny}});
            }
        }
    }
    cout << ans << "\n";

    return 0;
}

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