Submission #1254836

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254836		shawnchang51	Maze (JOI23_ho_t3)	C++17	0 / 100	0 ms	328 KiB

Main

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

struct Cell {
    int r, c;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int R, C, N;
    cin >> R >> C >> N;
    int Sr, Sc, Gr, Gc;
    cin >> Sr >> Sc >> Gr >> Gc;
    --Sr; --Sc; --Gr; --Gc; // convert to 0-based

    vector<string> grid(R);
    for (int i = 0; i < R; i++) cin >> grid[i];

    // Distance array: min stamp count to reach each cell
    vector<int> dist(R * C, INT_MAX);
    deque<int> dq;

    auto idx = [&](int r, int c) { return r * C + c; };

    // Starting point
    dist[idx(Sr, Sc)] = 0;
    dq.push_back(idx(Sr, Sc));

    // For each cell, precompute stamp top-left range that can paint it
    // Stamp top-left corner a,b must satisfy:
    //   a in [r - N + 1, r] and 0 <= a <= R - N
    //   b in [c - N + 1, c] and 0 <= b <= C - N
    vector<vector<pair<int,int>>> stampCover(R * C);

    for (int r = 0; r < R; r++) {
        int amin = max(0, r - N + 1);
        int amax = min(r, R - N);
        for (int c = 0; c < C; c++) {
            int bmin = max(0, c - N + 1);
            int bmax = min(c, C - N);
            auto &vec = stampCover[idx(r, c)];
            for (int a = amin; a <= amax; a++) {
                for (int b = bmin; b <= bmax; b++) {
                    vec.push_back({a, b});
                }
            }
        }
    }

    // For each stamp position (a,b), precompute cells it covers
    int totalStamps = (R - N + 1) * (C - N + 1);
    vector<vector<int>> stampCells(totalStamps);
    auto stampIdx = [&](int a, int b) { return a * (C - N + 1) + b; };

    for (int a = 0; a <= R - N; a++) {
        for (int b = 0; b <= C - N; b++) {
            auto &vec = stampCells[stampIdx(a, b)];
            vec.reserve(N * N);
            for (int dr = 0; dr < N; dr++) {
                for (int dc = 0; dc < N; dc++) {
                    int rr = a + dr, cc = b + dc;
                    vec.push_back(idx(rr, cc));
                }
            }
        }
    }

    vector<bool> usedStamp(totalStamps, false);

    // 0-1 BFS
    while (!dq.empty()) {
        int cur = dq.front();
        dq.pop_front();
        int r = cur / C, c = cur % C;
        if (r == Gr && c == Gc) {
            cout << dist[cur] << "\n";
            return 0;
        }
        // Move to adjacent white cells with cost 0
        static int dr[4] = {-1, 1, 0, 0};
        static int dc[4] = {0, 0, -1, 1};
        for (int k = 0; k < 4; k++) {
            int nr = r + dr[k], nc = c + dc[k];
            if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
            if (grid[nr][nc] == '.' && dist[idx(nr, nc)] > dist[cur]) {
                dist[idx(nr, nc)] = dist[cur];
                dq.push_front(idx(nr, nc));
            }
        }
        // Use stamps to paint black cells (cost +1)
        for (auto [a, b] : stampCover[cur]) {
            int si = stampIdx(a, b);
            if (usedStamp[si]) continue;
            usedStamp[si] = true;
            for (int cell : stampCells[si]) {
                if (dist[cell] > dist[cur] + 1) {
                    dist[cell] = dist[cur] + 1;
                    dq.push_back(cell);
                }
            }
        }
    }

    return 0;
}

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