Submission #987718

#	Time	Username	Problem	Language	Result	Execution time	Memory
987718		Zero_OP	Maze (JOI23_ho_t3)	C++14	62 / 100	98 ms	15840 KiB

Main

//no template practicing
#include<bits/stdc++.h>

using namespace std;

const int dx[4] = {0, 0, -1, +1};
const int dy[4] = {-1, 1, 0, 0};

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

    int R, C, N, rs, cs, rt, ct;
    cin >> R >> C >> N >> rs >> cs >> rt >> ct;
    --rs, --cs, --rt, --ct;
    vector<vector<char>> a(R, vector<char>(C));
    vector<vector<int>> d(R, vector<int>(C, -1));

    for(int i = 0; i < R; ++i){
        for(int j = 0; j < C; ++j){
            cin >> a[i][j];
        }
    }

    queue<pair<int, int>> white_queue;
    queue<tuple<int, int, int, int>> black_queue;

    white_queue.push({rs, cs});
    d[rs][cs] = 0;

    auto inside = [&](int r, int c){
        return -1 < r && r < R && -1 < c && c < C;
    };

    while(!white_queue.empty() || !black_queue.empty()){
        while(!white_queue.empty()){
            int r, c;
            tie(r, c) = white_queue.front(); white_queue.pop();

            for(int i = 0; i < 4; ++i){
                int nr = r + dx[i], nc = c + dy[i];
                if(inside(nr, nc) && d[nr][nc] == -1){
                    if(a[nr][nc] == '.'){
                        d[nr][nc] = d[r][c];
                        white_queue.push({nr, nc});
                    }
                    else{
                        d[nr][nc] = d[r][c] + 1;
                        black_queue.push({nr, nc, N - 1, N - 1});
                    }
                }
            }
        }

        while(!black_queue.empty()){
            int r, c, dist_r, dist_c;
            tie(r, c, dist_r, dist_c) = black_queue.front(); black_queue.pop();

            if(dist_r == 0 || dist_c == 0){
                white_queue.push({r, c});
            }

            for(int i = 0; i < 4; ++i){
                int nr = r + dx[i], nc = c + dy[i];
                int n_dist_r = dist_r - abs(dx[i]), n_dist_c = dist_c - abs(dy[i]);
                if(inside(nr, nc) && d[nr][nc] == -1 && n_dist_r >= 0 && n_dist_c >= 0){
                    d[nr][nc] = d[r][c];
                    black_queue.push({nr, nc, n_dist_r, n_dist_c});
                }
            }
        }
    }

    cout << d[rt][ct] << '\n';

    return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 19 / 19
• Subtask 3: 16 / 16
• Subtask 4: 19 / 19
• Subtask 5: 0 / 5
• Subtask 6: 0 / 19
• Subtask 7: 0 / 8
• Subtask 8: 0 / 6