Submission #1076897

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076897		dwuy	Maze (JOI23_ho_t3)	C++14	100 / 100	1803 ms	739988 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int MX = 3000006;
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};

struct vortex{
    int id;
    int d[MX];
    vortex(): id(0) {}

    void push_back(int x){
        id++;
        d[id] = x;
    }

    void pop_back(){
        if(id) id--;
    }

    void clear(){
        id = 0;
    }

    int gx(int i){
        return !i || i > id? -1 : d[i];
    }
};

int n, m, k;
int Sx, Sy, Ex, Ey;
vector<vector<int>> ttr;
vector<vector<int>> ttb;
vector<vector<int>> d;
string a[MX];
queue<pii> Q[2];

void nhap(){
    cin >> n >> m >> k;
    cin >> Sx >> Sy >> Ex >> Ey;
    ttr.assign(n + 5, vector<int>(m + 5, 0));
    ttb.assign(m + 5, vector<int>(n + 5, 0));
    for(int i=1; i<=n; i++){
        cin >> a[i];
        a[i] = ' ' + a[i];
        for(int j=1; j<=m; j++){
            ttr[i][j] = j + 1;
            ttb[j][i] = i + 1;
        }
    }
}

void solve(){
    d.assign(n + 5, vector<int>(m + 5, 1e9));
    d[Sx][Sy] = 0;
    Q[0].push({Sx, Sy});
    for(int f=0; f<n*m; f++){
        int c = f&1;
        vector<pii> vt;
        while(Q[c].size()){
            int x, y;
            tie(x, y) = Q[c].front();
            vt.push_back({x, y});
            Q[c].pop();
            for(int i=0; i<4; i++){
                int u = x + dx[i];
                int v = y + dy[i];
                if(u < 1 || u > n || v < 1 || v > m || a[u][v] == '#' || d[u][v] <= d[x][y]) continue;
                d[u][v] = d[x][y];
                Q[c].push({u, v});
            }
        }
        for(pii td: vt){
            int x, y;
            tie(x, y) = td;
            vector<int> vert;
            for(int i=max(1, x-k); i<=min(n, x+k);){
                vert.push_back(i);
                vector<int> hori;
                for(int j=max(1, y-k); j<=min(m, y+k);){
                    if((i == x - k || i == x + k) && (j == y - k || j == y + k)){
                        j = ttr[i][j];
                        continue;
                    }
                    hori.push_back(j);
                    if(d[i][j] > d[x][y] + 1){
                        d[i][j] = d[x][y] + 1;
                        Q[c^1].push({i, j});
                    }
                    j = ttr[i][j];
                }
                if(hori.size()){
                    int p = hori.back(); hori.pop_back();
                    for(int j: hori) ttr[i][j] = p;
                }
                i = ttb[y][i];
            }
            if(vert.size()){
                int p = vert.back(); vert.pop_back();
                for(int i: vert) ttb[y][i] = p;
            }
        }
    }
    cout << d[Ex][Ey];
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    nhap();
    solve();

    return 0;
}


/*

10 10 2
1 1
10 10
.##.#..##.
#..#.###.#
###.#.##..
..##..####
..###.##.#
###.#.###.
##.#.#####
##.....#.#
##.#.#.#.#
##.#.####.

*/

• 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