Submission #768650

#	Time	Username	Problem	Language	Result	Execution time	Memory
768650		green_gold_dog	Maze (JOI23_ho_t3)	C++17	27 / 100	2077 ms	23964 KiB

Main

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll INF = 1'000'000'000;

template<typename T>
bool assign_min(T& a, T b) {
        if (a > b) {
                a = b;
                return true;
        }
        return false;
}

template<typename T>
bool assign_max(T& a, T b) {
        if (a < b) {
                a = b;
                return true;
        }
        return false;
}

struct segment_tree {
};

void solve() {
        ll n, r, c;
        cin >> r >> c >> n;
        ll sx, sy, gx, gy;
        cin >> sx >> sy >> gx >> gy;
        sx--;
        sy--;
        gx--;
        gy--;
        vector<vector<bool>> arr(r, vector<bool>(c, false));
        vector<vector<ll>> dist(r, vector<ll>(c, INF));
        for (ll i = 0; i < r; i++) {
                string s;
                cin >> s;
                for (ll j = 0; j < c; j++) {
                        if (s[j] == '.') {
                                arr[i][j] = true;
                        }
                }
        }
        dist[sx][sy] = 0;
        deque<pair<ll, ll>> d;
        d.emplace_back(sx, sy);
        while (!d.empty()) {
                auto[x, y] = d.front();
                if (x == gx && y == gy) {
                        break;
                }
                d.pop_front();
                if (x > 0) {
                        if (arr[x - 1][y] && assign_min(dist[x - 1][y], dist[x][y])) {
                                d.emplace_front(x - 1, y);
                        }
                }
                if (x + 1 < r) {
                        if (arr[x + 1][y] && assign_min(dist[x + 1][y], dist[x][y])) {
                                d.emplace_front(x + 1, y);
                        }
                }
                if (y > 0) {
                        if (arr[x][y - 1] && assign_min(dist[x][y - 1], dist[x][y])) {
                                d.emplace_front(x, y - 1);
                        }
                }
                if (y + 1 < c) {
                        if (arr[x][y + 1] && assign_min(dist[x][y + 1], dist[x][y])) {
                                d.emplace_front(x, y + 1);
                        }
                }
                for (ll i = -n; i <= n; i++) {
                        for (ll j = -n; j <= n; j++) {
                                if (abs(i) == n && abs(j) == n) {
                                        continue;
                                }
                                if (x + i >= 0 && x + i < r && y + j >= 0 && y + j < c) {
                                        if (assign_min(dist[x + i][y + j], dist[x][y] + 1)) {
                                                d.emplace_back(x + i, y + j);
                                        }
                                }
                        }
                }
        }
        cout << dist[gx][gy] << '\n';
}

int main() {
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        solve();
}

• Subtask 1: 8 / 8
• Subtask 2: 19 / 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