Submission #1137307

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137307		Sharky	Maze (JOI23_ho_t3)	C++20	100 / 100	447 ms	293864 KiB

Main

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

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

#define int long long
#define fi first
#define se second

const int dx[4] = {0, -1, 1, 0}, dy[4] = {1, 0, 0, -1};
const int Dx[8] = {-1, 0, 1, -1, 1, -1, 0, 1}, Dy[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
const int inf = 1e9;

struct state {
    int x, y, d1, d2;
};

bool cmp(pair<int, int> x, pair<int, int> y) { // is y better than x
    if (y.first < x.first) return true;
    if (y.first == x.first && y.second > x.second) return true;
    return false;
};

void solve() {
    int r, c, n, sr, sc, gr, gc;
    cin >> r >> c >> n >> sr >> sc >> gr >> gc;
    vector<vector<char>> a(r+1, vector<char> (c+1));
    for (int i = 1; i <= r; i++) for (int j = 1; j <= c; j++) cin >> a[i][j];
    vector<vector<pair<int, int>>> di(r+1, vector<pair<int, int>> (c+1, {inf, inf}));
    vector<vector<bool>> vis(r+1, vector<bool> (c+1, 0));
    deque<state> q;
    q.push_back({sr, sc, 0, 0});
    di[sr][sc] = {0, 0};
    while (!q.empty()) {
        auto [x, y, d1, d2] = q.front();
        q.pop_front();
        if (x == gr && y == gc) {
            cout << d1 << '\n';
            return;
        }
        if (di[x][y] != make_pair(d1, d2)) continue;
        if (d2) {
            for (int i = 0; i < 8; i++) {
                int nx = x + Dx[i], ny = y + Dy[i];
                if (nx < 1 || nx > r || ny < 1 || ny > c) continue;
                if (cmp(di[nx][ny], make_pair(d1, d2-1))) {
                    di[nx][ny] = make_pair(d1, d2-1);
                    q.push_back({nx, ny, d1, d2-1});
                }
            }
        } else {
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i], ny = y + dy[i];
                if (nx < 1 || nx > r || ny < 1 || ny > c) continue;
                if (a[nx][ny] == '#') {
                    if (cmp(di[nx][ny], make_pair(d1+1, n-1))) {
                        di[nx][ny] = make_pair(d1+1, n-1);
                        q.push_back({nx, ny, d1+1, n-1});
                    }
                } else {
                    if (cmp(di[nx][ny], make_pair(d1, 0))) {
                        di[nx][ny] = make_pair(d1, 0);
                        q.push_front({nx, ny, d1, 0});
                    }
                }
            }
        }
    }
}

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int test = 1;
    // cin >> test;
    while (test--) solve();
}

• 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