Submission #932887

#	Time	Username	Problem	Language	Result	Execution time	Memory
932887		Pring	Maze (JOI23_ho_t3)	C++17	100 / 100	1020 ms	399404 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 = 6000005, LAYER = 8;
const pii D[4] = {mp(1, 0), mp(-1, 0), mp(0, 1), mp(0, -1)};
int R, C, N;
pii sr, to;
vector<string> s;
int K;
int dis[MXN * LAYER];
vector<int> v0, v1;
int cnt;

inline int cvt(pii p) {
    return p.fs * C + p.sc;
}

inline pii cvt(int x) {
    return mp(x / C, x % C);
}

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

inline bool OUT(pii p) {
    if (!(0 <= p.fs && p.fs < R)) return true;
    if (!(0 <= p.sc && p.sc < C)) return true;
    return false;
}

namespace EDGE {
    inline int cvt3(int l, int x, int y) {
        return l * R * C + x * C + y;
    }

    inline void PUSH_EDGE(int sr, int to, int val) {
        (val ? v1 : v0).push_back(to);
    }

    void E0(pii p) {
        FOR(d, 0, 4) {
            pii nxt = p + D[d];
            if (OUT(nxt)) continue;
            if (s[p.fs][p.sc] == '.' && s[nxt.fs][nxt.sc] == '.') PUSH_EDGE(cvt3(0, p.fs, p.sc), cvt3(0, nxt.fs, nxt.sc), 0);
            PUSH_EDGE(cvt3(0, p.fs, p.sc), cvt3(1, nxt.fs, nxt.sc), 1);
        }
    }

    void E1(pii p) {
        int l = max(0, p.fs - (N - 1)), r = min(R, p.fs + N);
        int y = p.sc, sr = cvt3(1, p.fs, p.sc);
        if (r - l == K) {
            PUSH_EDGE(sr, cvt3(2, l, y), 0);
            PUSH_EDGE(sr, cvt3(3, r - 1, y), 0);
            return;
        }
        if (r == R) {
            PUSH_EDGE(sr, cvt3(2, l, y), 0);
            int m = (l ? (l - 1) / K * K + K : 0);
            if (m < R) PUSH_EDGE(sr, cvt3(2, m, y), 0);
            return;
        }
        PUSH_EDGE(sr, cvt3(3, r - 1, y), 0);
    }

    void E2(pii p) {
        PUSH_EDGE(cvt3(2, p.fs, p.sc), cvt3(4, p.fs, p.sc), 0);
        if (p.fs == R - 1 || (p.fs + 1) % K == 0) return;
        PUSH_EDGE(cvt3(2, p.fs, p.sc), cvt3(2, p.fs + 1, p.sc), 0);
    }

    void E3(pii p) {
        PUSH_EDGE(cvt3(3, p.fs, p.sc), cvt3(4, p.fs, p.sc), 0);
        if (p.fs % K == 0) return;
        PUSH_EDGE(cvt3(3, p.fs, p.sc), cvt3(3, p.fs - 1, p.sc), 0);
    }

    void E4(pii p) {
        int l = max(0, p.sc - (N - 1)), r = min(C, p.sc + N);
        int x = p.fs, sr = cvt3(4, p.fs, p.sc);
        if (r - l == K) {
            PUSH_EDGE(sr, cvt3(5, x, l), 0);
            PUSH_EDGE(sr, cvt3(6, x, r - 1), 0);
            return;
        }
        if (r == C) {
            PUSH_EDGE(sr, cvt3(5, x, l), 0);
            int m = (l ? (l - 1) / K * K + K : 0);
            if (m < C) PUSH_EDGE(sr, cvt3(5, x, m), 0);
            return;
        }
        PUSH_EDGE(sr, cvt3(6, x, r - 1), 0);
    }

    void E5(pii p) {
        PUSH_EDGE(cvt3(5, p.fs, p.sc), cvt3(7, p.fs, p.sc), 0);
        if (p.sc + 1 == C || (p.sc + 1) % K == 0) return;
        PUSH_EDGE(cvt3(5, p.fs, p.sc), cvt3(5, p.fs, p.sc + 1), 0);
    }

    void E6(pii p) {
        PUSH_EDGE(cvt3(6, p.fs, p.sc), cvt3(7, p.fs, p.sc), 0);
        if (p.sc % K == 0) return;
        PUSH_EDGE(cvt3(6, p.fs, p.sc), cvt3(6, p.fs, p.sc - 1), 0);
    }

    void E7(pii p) {
        PUSH_EDGE(cvt3(7, p.fs, p.sc), cvt3(0, p.fs, p.sc), 0);
        FOR(d, 0, 4) {
            pii nxt = p + D[d];
            if (OUT(nxt) || s[nxt.fs][nxt.sc] == '#') continue;
            PUSH_EDGE(cvt3(7, p.fs, p.sc), cvt3(0, nxt.fs, nxt.sc), 0);
        }
    }

    void BUILD(int id) {
        int l = id / (C * R);
        pii p = cvt(id % (C * R));
        // debug(l, p.fs, p.sc);
        if (l == 0) E0(p);
        else if (l == 1) E1(p);
        else if (l == 2) E2(p);
        else if (l == 3) E3(p);
        else if (l == 4) E4(p);
        else if (l == 5) E5(p);
        else if (l == 6) E6(p);
        else E7(p);
    }
}

namespace BFS {
    void GO(int sr, int to) {
        fill(dis, dis + R * C * LAYER, -1);
        v0.push_back(sr);
        while (v0.size()) {
            for (int i = 0; i < v0.size(); i++) {
                int id = v0[i];
                if (dis[id] != -1) continue;
                dis[id] = cnt;
                if (id == to) return;
                EDGE::BUILD(id);
            }
            swap(v0, v1);
            v1.clear();
            cnt++;
        }
    }
}

void miku() {
    cin >> R >> C >> N >> sr.fs >> sr.sc >> to.fs >> to.sc;
    sr.fs--, sr.sc--, to.fs--, to.sc--;
    K = N * 2 - 1;
    s.resize(R);
    FOR(i, 0, R) cin >> s[i];
    // EDGE::BUILD();
    BFS::GO(cvt(sr), cvt(to));
    cout << dis[cvt(to)] << '\n';
}

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

Compilation message (stderr)

Main.cpp: In function 'void BFS::GO(int, int)':
Main.cpp:153:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |             for (int i = 0; i < v0.size(); i++) {
      |                             ~~^~~~~~~~~~~

• 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