Submission #1357071

#	Time	Username	Problem	Language	Result	Execution time	Memory
1357071		guardianec	Maze (JOI23_ho_t3)	C++20	51 / 100	2097 ms	28784 KiB

Main

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

ll r,c,n;
ll calc(ll i, ll j) {
    return i*c+j;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    
    cin >> r >> c >> n;
    ll s1,s2,g1,g2;
    cin >> s1 >> s2 >> g1 >> g2;
    s1--; s2--; g1--; g2--;

    vector<string> a(r);
    for (int i=0; i<r; i++) {
        cin >> a[i];
    }

    vector<ll> dist(r*c, 1e18);
    vector<ll> dist1(r*c, 1e18);

    deque<ll> dq, sq;
    dq.push_front(calc(s1, s2));
    dist[calc(s1,s2)] = 0;
    dist1[calc(s1,s2)]=n-1;
    sq.push_back(calc(s1,s2));

    vector<ll> di = {-1, 1, 0, 0, -1, -1, 1, 1};
    vector<ll> dj = {0, 0, -1, 1, -1, 1, -1, 1};
    while(!dq.empty()) {
        ll u = dq.front();
        dq.pop_front();

        ll i = u/c; ll j = u%c;
        ll d = dist[u];
        ll s = dist1[u];
        if (s<n-1) {
            for (int idx=0; idx<8; idx++) {
                ll i1 = i+di[idx];
                ll j1 = j+dj[idx];
                if (i1>=0 && i1<r && j1>=0 && j1<c) {
                    ll v = calc(i1, j1);
                    if (dist[v]>d || (dist[v]==d && dist1[v]>s+1)) {
                        dist[v] = d;
                        dist1[v] = s+1;
                        dq.push_front(v);
                    }
                }
            }
        }

        for (int idx=0; idx<4; idx++) {
            ll i1 = i+di[idx];
            ll j1 = j+dj[idx];
            if (i1>=0 && i1<r && j1>=0 && j1<c) {
                ll v = calc(i1, j1);

                if (a[i1][j1]=='.') {
                    if (dist[v]>d || (dist[v]==d && dist1[v]>n-1)) {
                        dist[v] = d;
                        dist1[v] = n-1;
                        dq.push_front(v);
                    }
                }

                if (dist[v]>d+1 || (dist[v]==d+1 && dist1[v]>0)) {
                    dist[v] = d+1;
                    dist1[v] = 0;
                    dq.push_back(v);
                }
            }
        }
    }

    cout << dist[calc(g1,g2)];
}

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