Submission #1153646

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153646		vladilius	Maze (JOI23_ho_t3)	C++20	0 / 100	1 ms	328 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int r, c, n, sx, sy, ex, ey; cin>>r>>c>>n>>sx>>sy>>ex>>ey;
    vector<vector<char>> a(r + 1, vector<char>(c + 1));
    vector<vector<vector<pii>>> adj(r + 1, vector<vector<pii>>(c + 1));
    for (int i = 1; i <= r; i++){
        for (int j = 1; j <= c; j++){
            cin>>a[i][j];
            if (i > 1) adj[i][j].pb({i - 1, j});
            if (j > 1) adj[i][j].pb({i, j - 1});
            if (i < r) adj[i][j].pb({i + 1, j});
            if (j < c) adj[i][j].pb({i, j + 1});
        }
    }
    
    vector<vector<int>> dist(r + 1, vector<int>(c + 1, 1e9));
    queue<pii> q, q1; q.push({sx, sy});
    vector<int> l1(r + 1, c + 1), r1(r + 1, 0);
    l1[sx] = r1[sx] = sy; dist[sx][sy] = 0;
    
    auto move = [&](int x, int y){
        if (a[x][y] == '.') q1.push({x, y});
        for (auto [x1, y1]: adj[x][y]){
            if (a[x1][y1] == '.'){
                if (dist[x1][y1] == 1e9){
                    dist[x1][y1] = dist[x][y];
                    l1[x1] = min(l1[x1], y1);
                    r1[x1] = max(r1[x1], y1);
                    q.push({x1, y1});
                }
                q1.push({x1, y1});
            }
        }
        while (!q1.empty()){
            auto [x1, y1] = q1.front(); q1.pop();
            for (auto [x2, y2]: adj[x1][y1]){
                if (a[x2][y2] == '.' && dist[x2][y2] == 1e9){
                    dist[x2][y2] = dist[x][y];
                    l1[x2] = min(l1[x2], y2);
                    r1[x2] = max(r1[x2], y2);
                    q.push({x2, y2});
                    q1.push({x2, y2});
                }
            }
        }
    };
    
    move(sx, sy);
    
    while (!q.empty()){
        auto [x, y] = q.front(); q.pop();
        if (x == ex && y == ey){
            cout<<dist[x][y]<<"\n";
            return 0;
        }
        
        int L = y - n, R = y + n;
        for (int i = max(1, x - n); i <= min(r, x + n); i++){
            int L1 = max(1, L + (abs(i - x) == n)), R1 = min(c, R - (abs(i - x) == n));
            for (int j = min(l1[i] - 1, R1); j >= L1; j--){
                dist[i][j] = dist[x][y] + 1;
                q.push({i, j});
                move(i, j);
                l1[i] = min(l1[i], j);
                r1[i] = max(r1[i], j);
            }
            for (int j = max(L1, r1[i] + 1); j <= R1; j++){
                dist[i][j] = dist[x][y] + 1;
                q.push({i, j});
                move(i, j);
                l1[i] = min(l1[i], j);
                r1[i] = max(r1[i], j);
            }
        }
    }
}

• 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