Submission #1254837

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

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 1e9;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int R,C,N;
    if(!(cin>>R>>C>>N)) return 0;
    int Sr,Sc,Gr,Gc;
    cin>>Sr>>Sc>>Gr>>Gc;
    --Sr; --Sc; --Gr; --Gc;
    vector<string> A(R);
    for(int i=0;i<R;i++) cin>>A[i];

    if (Sr==Gr && Sc==Gc) { cout<<0<<"\n"; return 0; }

    int H = R - N + 1; // stamp rows
    int W = C - N + 1; // stamp cols
    // total stamps
    long long totalStamps = 1LL * H * W;

    // Node indexing:
    // cell nodes: 0 .. R*C-1
    // stamp nodes: baseStamp = R*C .. R*C + totalStamps -1
    int cells = R * C;
    long long baseStamp = cells;

    // dist array for all nodes (cells + stamps)
    // use int if fits; INF sentinel
    vector<int> dist;
    try {
        dist.assign(cells + (int)totalStamps, INF);
    } catch(...) {
        // fallback just in case (shouldn't happen within problem limits)
        return 0;
    }

    // DSU-like "find-next" arrays:
    // 1) For stamp rows: for each stamp-row (H rows), we keep array size W+1
    //    parentStampAll size = H * (W+1)
    // index base for row a: base = a*(W+1)
    vector<int> parentStamp; 
    if (H>0 && W>0) parentStamp.assign((size_t)H * (W + 1), 0);

    auto stampBase = [&](int a){ return a * (W + 1); };

    // init parentStamp
    for(int a=0;a<H;a++){
        int base = stampBase(a);
        for(int b=0;b<=W;b++) parentStamp[base + b] = base + b;
    }
    // find-next for stamp (global array)
    function<int(int)> findStamp = [&](int x)->int{
        int r = x;
        while(parentStamp[r] != r){
            parentStamp[r] = parentStamp[parentStamp[r]];
            r = parentStamp[r];
        }
        return r;
    };

    // 2) For cell rows: for each original grid row (R rows), keep array size C+1
    // parentCellAll size = R * (C+1)
    vector<int> parentCell;
    parentCell.assign((size_t)R * (C + 1), 0);
    auto cellBase = [&](int row){ return row * (C + 1); };
    for(int i=0;i<R;i++){
        int base = cellBase(i);
        for(int j=0;j<=C;j++) parentCell[base + j] = base + j;
    }
    function<int(int)> findCell = [&](int x)->int{
        int r = x;
        while(parentCell[r] != r){
            parentCell[r] = parentCell[parentCell[r]];
            r = parentCell[r];
        }
        return r;
    };

    auto cellId = [&](int r,int c){ return r * C + c; };
    auto stampId = [&](int a,int b){ return (int)(baseStamp + a * 1LL * W + b); };

    deque<int> dq;

    // initialize start cell
    int sId = cellId(Sr,Sc);
    dist[sId] = 0;
    dq.push_front(sId);
    // mark start as "removed" from cell DSU (so stamp won't iterate it again)
    {
        int base = cellBase(Sr);
        int pos = findCell(base + Sc);
        if(pos == base + Sc) parentCell[pos] = findCell(pos + 1);
    }

    // BFS
    const int dr[4] = {-1,1,0,0};
    const int dc[4] = {0,0,-1,1};

    while(!dq.empty()){
        int u = dq.front(); dq.pop_front();
        int du = dist[u];
        if(u == cellId(Gr,Gc)){
            cout<<du<<"\n";
            return 0;
        }
        if(u < cells){
            // cell node
            int r = u / C, c = u % C;
            // move to 4-neighbors if white (cost 0)
            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(A[nr][nc]=='.'){
                    int v = cellId(nr,nc);
                    if(dist[v] > du){
                        dist[v] = du;
                        dq.push_front(v);
                        // remove from cell DSU if present
                        int base = cellBase(nr);
                        int pos = findCell(base + nc);
                        if(pos == base + nc) parentCell[pos] = findCell(pos + 1);
                    }
                }
            }
            // trigger stamps that cover this cell (cost 1)
            // a in [r-N+1, r] ∩ [0, H-1]
            // b in [c-N+1, c] ∩ [0, W-1]
            if(H>0 && W>0){
                int a_low = max(0, r - N + 1);
                int a_high = min(r, R - N);
                int b_low = max(0, c - N + 1);
                int b_high = min(c, C - N);
                if(a_low <= a_high && b_low <= b_high){
                    for(int a = a_low; a <= a_high; ++a){
                        int base = stampBase(a);
                        int pos = findStamp(base + b_low);
                        while(true){
                            int col = pos - base;
                            if(col > b_high) break;
                            int s = stampId(a, col);
                            if(dist[s] > du + 1){
                                dist[s] = du + 1;
                                dq.push_back(s);
                            }
                            // remove this stamp column from DSU (so we won't process it again)
                            parentStamp[pos] = findStamp(pos + 1);
                            pos = findStamp(pos);
                        }
                    }
                }
            }
        } else {
            // stamp node
            int sid = u - cells;
            int a = sid / W;
            int b = sid % W;
            // stamp covers rows a..a+N-1, cols b..b+N-1
            for(int i = a; i < a + N; ++i){
                int base = cellBase(i);
                int pos = findCell(base + b);
                while(true){
                    int col = pos - base;
                    if(col >= C) break; // sentinel
                    if(col > b + N - 1) break;
                    int v = cellId(i, col);
                    if(dist[v] > dist[u]){
                        dist[v] = dist[u];
                        dq.push_front(v);
                    }
                    // remove this cell from DSU so future stamps skip it
                    parentCell[pos] = findCell(pos + 1);
                    pos = findCell(pos);
                }
            }
        }
    }

    // If BFS ends without reaching goal, print dist[goal] (might be INF)
    int ans = dist[cellId(Gr,Gc)];
    if(ans==INF) cout<<-1<<"\n"; // problem statement guarantees it's possible by stamping enough times, but safe fallback
    else cout<<ans<<"\n";
    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