Submission #1249755

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249755		norman165	Maze (JOI23_ho_t3)	C++20	100 / 100	431 ms	119324 KiB

Main

#include <bits/stdc++.h>

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define int long long
#define yes() cout << "YES\n"
#define no() cout << "NO\n"

using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;

const int inf = 1e18;
const int mod = 1e9 + 7;
const int maxn = 1e7 + 5e6;
const int mod1 = 998244353;
const int mod2 = 1e18 + 1;
const int mod3 = 1e9 + 9;
const int mod4 = 333333333;
const int mod5 = 200000;
const int mod6 = 10007;
const int k = 300;
const int w = 1e5;
const ld EPS = 1e-8;

int LOG = 30;

struct e {
    int x, y, p, q;
};

void solve() {
    int k, n, m;
    cin >> n >> m >> k;

    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;

    x1--, y1--, x2--, y2--;
    vector<vector<int>> d(n, vector<int> (m, inf));
    d[x1][y1] = 0;

    vector<string> a(n);
    for (auto& i : a) cin >> i;

    queue<pair<int, int>> q1;
    queue<e> q2;
    vector<pair<int, int>> tmp = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    q1.push({x1, y1});

    while (q1.size()) {
        while (q1.size()) {
            auto [x, y] = q1.front();
            q1.pop();

            for (auto& [dx, dy] : tmp) {
                int nx = x + dx, ny = y + dy;
                if (!(0 <= nx && nx < n && 0 <= ny && ny < m && d[nx][ny] == inf)) continue;
                if (a[nx][ny] == '.') {
                    d[nx][ny] = d[x][y];
                    q1.push({nx, ny});
                } else {
                    d[nx][ny] = d[x][y] + 1;
                    q2.push({nx, ny, 0, 0});
                }
            }
        }

        while (q2.size()) {
            auto [x, y, p, q] = q2.front();
            q2.pop();

            if (p == k - 1 || q == k - 1) q1.push({x, y});
            for (auto& [dx, dy] : tmp) {
                int nx = x + dx, ny = y + dy;
                if (!(0 <= nx && nx < n && 0 <= ny && ny < m && d[nx][ny] == inf)) continue;
                if (p + abs(dx) < k && q + abs(dy) < k) {
                    d[nx][ny] = d[x][y];
                    q2.push({nx, ny, p + abs(dx), q + abs(dy)});
                }
            }
        }
    }

    cout << d[x2][y2] << "\n";
}

signed main() {
    // cout.precision(16);

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    // cin >> t;

    while (t--) {
        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