Submission #1037423

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037423		aaaaaarroz	Maze (JOI23_ho_t3)	C++17	100 / 100	352 ms	68564 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 main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m, k, r1, c1, r2, c2;
    cin >> n >> m >> k >> r1 >> c1 >> r2 >> c2;
    --r1, --c1, --r2, --c2;
    vector<vector<int>> d(n, vector<int>(m, -1));
    vector<vector<char>> a(n, vector<char>(m));
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j){
            cin >> a[i][j];
        }
    }
    queue<pair<int, int>> q1;
    queue<tuple<int, int, int, int>> q2;
    q1.push({r1, c1});
    d[r1][c1] = 0;
    auto inside = [&](int x, int y){
        return -1 < x && x < n && -1 < y && y < m;
    };
    while(!q1.empty() || !q2.empty()){
        while(!q1.empty()){
            int x, y;
            tie(x, y) = q1.front(); q1.pop();
            for(int i = 0; i < 4; ++i){
                int new_x = x + dx[i];
                int new_y = y + dy[i];
                if(inside(new_x, new_y) && d[new_x][new_y] == -1){
                    if(a[new_x][new_y] == '.'){
                        d[new_x][new_y] = d[x][y];
                        q1.push({new_x, new_y});
                    }
                    else{
                        d[new_x][new_y] = d[x][y] + 1;
                        q2.push({new_x, new_y, k - 1, k - 1});
                    }
                }
            }
        }
        while(!q2.empty()){
            int x, y, sx, sy;
            tie(x, y, sx, sy) = q2.front(); q2.pop();
 
            if(sx == 0 || sy == 0){
                q1.push({x, y});
            }
            for(int i = 0; i < 4; ++i){
                int new_x = x + dx[i];
                int new_y = y + dy[i];
                int new_sx = sx - abs(dx[i]);
                int new_sy = sy - abs(dy[i]);
                if(inside(new_x, new_y) && d[new_x][new_y] == -1 && new_sx >= 0 && new_sy >= 0){
                    d[new_x][new_y] = d[x][y];
                    q2.push({new_x, new_y, new_sx, new_sy});
                }
            }
        }
    }
    cout << d[r2][c2] << '\n';
    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