제출 #1291156

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1291156		nguyenkhangninh99	Maze (JOI23_ho_t3)	C++20	100 / 100	1117 ms	517124 KiB

Main

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

const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};
int r, c, k; 

bool inside(int x, int y){
    return (1 <= x && x <= r && 1 <= y && y <= c);
}

void solve(){   
    cin >> r >> c >> k;

    vector<vector<int>> d(r + 1, vector<int>(c + 1, -1));
    vector<vector<int>> cell(r + 1, vector<int>(c + 1, 0));
    vector<vector<int>> vis(r + 1, vector<int>(c + 1, 0));

    int sx, sy, tx, ty; 
    cin >> sx >> sy >> tx >> ty;

    for(int i = 1; i <= r; i++){
        for(int j = 1; j <= c; j++){
            char x; cin >> x;
            if(x == '#') cell[i][j] = 1;
        }
    }

    vector<vector<int>> rowNext(r + 1, vector<int>(c + 2));
    vector<vector<int>> colNext(c + 1, vector<int>(r + 2));

    for(int i = 1; i <= r; i++){
        for(int j = 1; j <= c + 1; j++){
            rowNext[i][j] = j;
        }
    }
    for(int j = 1; j <= c; j++){
        for(int i = 1; i <= r + 1; i++){
            colNext[j][i] = i;
        }
    }

    function<int(int, int)> findRow = [&](int row, int col) -> int {
        if(col > c) return c + 1;
        if(rowNext[row][col] == col) return col;
        return rowNext[row][col] = findRow(row, rowNext[row][col]);
    };

    function<int(int, int)> findCol = [&](int col, int row) -> int {
        if(row > r) return r + 1;
        if(colNext[col][row] == row) return row;
        return colNext[col][row] = findCol(col, colNext[col][row]);
    };

    auto del = [&](int x, int y){
        rowNext[x][y] = findRow(x, y + 1);
        colNext[y][x] = findCol(y, x + 1);
    };

    deque<pair<int, int>> q;
    q.push_back({sx, sy});
    d[sx][sy] = 0;
    del(sx, sy); 

    while(q.size()){
        auto [x, y] = q.front();
        q.pop_front();
        if(vis[x][y]) continue;
        vis[x][y] = 1;

        for(int i = 0; i < 4; i++){
            int nx = x + dx[i], ny = y + dy[i];
            if(inside(nx, ny)){
                if(!cell[nx][ny] && (d[nx][ny] > d[x][y] || d[nx][ny] == -1)){
                    d[nx][ny] = d[x][y];
                    q.push_front({nx, ny});
                    del(nx, ny);
                }
            }
        }

        for(int nny: {y - k, y + k}){
            if(1 <= nny && nny <= c){
                int lbound = max(1, x - (k - 1));
                int rbound = min(r, x + (k - 1));

                int nnx = findCol(nny, lbound);
                while(nnx <= rbound){
                    if(d[nnx][nny] == -1){
                        d[nnx][nny] = d[x][y] + 1;
                        q.push_back({nnx, nny});
                    }
                    del(nnx, nny);
                    nnx = findCol(nny, nnx + 1);
                }
            }
        }

        for(int nnx: {x - k, x + k}){
            if(1 <= nnx && nnx <= r){
                int lbound = max(1, y - (k - 1));
                int rbound = min(c, y + (k - 1));

                int nny = findRow(nnx, lbound);
                while(nny <= rbound){
                    if(d[nnx][nny] == -1){
                        d[nnx][nny] = d[x][y] + 1;
                        q.push_back({nnx, nny});
                    }
                    del(nnx, nny);
                    nny = findRow(nnx, nny + 1);
                }
            }
        }

        if(abs(tx - x) <= k && abs(ty - y) <= k){
            if(!(abs(tx - x) == k && abs(ty - y) == k)){
                if(d[tx][ty] == -1 || d[tx][ty] > d[x][y] + 1){
                    d[tx][ty] = d[x][y] + 1;
                    q.push_back({tx, ty});
                }
            }
        }
    }

    cout << d[tx][ty];
}

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

    solve();
    return 0;
}

• 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