Submission #931520

#	Time	Username	Problem	Language	Result	Execution time	Memory
931520		Pring	Maze (JOI23_ho_t3)	C++17	0 / 100	1 ms	456 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#ifdef MIKU
#define debug(x...) cout << "[" << #x << "] : ", dout(x)
void dout() { cout << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

#define int long long
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
typedef pair<int, int> pii;

const int MXN = 1500005, INF = 3.9e18;
int r, c, n;
pii sr, to;
pii dd[4] = {mp(1LL, 0LL), mp(-1LL, 0LL), mp(0LL, 1LL), mp(0LL, -1LL)};
vector<string> s;
vector<vector<pii>> edge;
vector<int> dis;
priority_queue<pii, vector<pii>, greater<pii>> pq;

inline int f(pii p) {
    return p.fs * r + p.sc;
}

inline pii f(int x) {
    return mp(x / r, x % r);
}

bool OUT(pii p) {
    if (p.fs < 0 || r <= p.fs) return true;
    if (p.fs < 0 || c <= p.sc) return true;
    return false;
}

pii operator+(pii a, pii b) {
    return mp(a.fs + b.fs, a.sc + b.sc);
}

pii operator-(pii a, pii b) {
    return mp(a.fs - b.fs, a.sc - b.sc);
}

void BUILD_EDGE() {
    edge.resize(r * c);
    FOR(i, 0, r * c) {
        pii now = f(i);
        FOR(d, 0, 4) {
            if (OUT(now + dd[d])) continue;
            edge[i].push_back(mp((s[now.fs][now.sc] == '#' ? 1LL : 0LL), f(now + dd[d])));
        }
    }
}

// void BUILD_FRAME() {
//     auto ADD = [&](pii x, int cnt) -> void {
//         if (OUT(x)) return;
//         edge[x].push_back()
//     };
//     FOR(i, 0, r - n + 1) FOR(j, 0, c - n + 1) {
//         int cnt = edge.size();
//         edge.push_back(vector<pii>());
//         FOR(k, 0, n) {
//         }
//     }
// }

void DIJKSTRA(int sr, int to) {
    dis = vector<int>(r * c, INF);
    pq.push(mp(0LL, sr));
    while (pq.size()) {
        int len = pq.top().fs, id = pq.top().sc;
        pq.pop();
        if (dis[id] != INF) continue;
        dis[id] = len;
        for (auto &i : edge[id]) {
            if (dis[i.sc] < INF) continue;
            pq.push(mp(i.fs + len, i.sc));
        }
    }
}

void miku() {
    cin >> r >> c >> n >> sr.fs >> sr.sc >> to.fs >> to.sc;
    sr.fs--;
    sr.sc--;
    to.fs--;
    to.sc--;
    s.resize(r);
    for (auto &i : s) cin >> i;
    BUILD_EDGE();
    // BUILD_FRAME();
    DIJKSTRA(f(sr), f(to));
    cout << dis[f(to)] << '\n';
}

int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(iostream::failbit);
    miku();
    return 0;
}

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