Submission #941659

#	Time	Username	Problem	Language	Result	Execution time	Memory
941659		peterandvoi	Maze (JOI23_ho_t3)	C++17	100 / 100	440 ms	68464 KiB

Main

#include <bits/stdc++.h>

using namespace std;

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

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    #ifdef ngu
    freopen("test.inp", "r", stdin);
    freopen("test.out", "w", stdout);
    #endif
    int r, c, n;
    cin >> r >> c >> n;
    vector<vector<char>> a(r, vector<char>(c));
    vector<vector<int>> d(r, vector<int>(c, -1));
    int sr, sc, gr, gc;
    cin >> sr >> sc >> gr >> gc;
    sr--; sc--; gr--; gc--;
    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < c; ++j) {
            cin >> a[i][j];
        }
    }
    auto inside = [&](int i, int j) {
        return 0 <= i && i < r && 0 <= j && j < c;
    };
    queue<pair<int, int>> W;
    queue<tuple<int, int, int, int>> B;
    W.emplace(sr, sc);
    d[sr][sc] = 0;
    while (W.size() || B.size()) {
        while (W.size()) {
            auto [x, y] = W.front();
            W.pop();
            for (int dr = 0; dr < 4; ++dr) {
                int i = x + dx[dr], j = y + dy[dr];
                if (inside(i, j) && d[i][j] == -1) {
                    if (a[i][j] == '.') {
                        d[i][j] = d[x][y];
                        W.emplace(i, j);
                    } else {
                        d[i][j] = d[x][y] + 1;
                        B.emplace(i, j, n - 1, n - 1);
                    }
                }
            }
        }
        while (B.size()) {
            auto [x, y, cx, cy] = B.front();
            B.pop();
            if (cx == 0 || cy == 0) {
                W.emplace(x, y);
            }
            for (int dr = 0; dr < 4; ++dr) {
                int i = x + dx[dr], j = y + dy[dr];
                int ci = cx - abs(dx[dr]), cj = cy - abs(dy[dr]);
                if (inside(i, j) && d[i][j] == -1 && ci >= 0 && cj >= 0) {
                    d[i][j] = d[x][y];
                    B.emplace(i, j, ci, cj);
                }
            }
        }
    }
    cout << d[gr][gc];
}

• 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