Submission #727423

#	Time	Username	Problem	Language	Result	Execution time	Memory
727423		model_code	Maze (JOI23_ho_t3)	C++17	100 / 100	572 ms	147180 KiB

Main

#include <array>
#include <climits>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    int R, C, K, Sr, Sc, Gr, Gc;
    cin >> R >> C >> K >> Sr >> Sc >> Gr >> Gc;
    K = 1 - K; Sr--; Sc--; Gr--; Gc--;
    vector<string> A(R);
    for(string& a : A) {
        cin >> a;
        for(char& c : a) c = c == '#';
    }

    // {ここに辿り着くまでに必要な塗りつぶし回数, 最後の塗りつぶしによって行ける縦の移動量, 最後の塗りつぶしによって行ける横の移動量} を持つ
    // 各レイヤー 3 フェーズの BFS
    // 1. 4 方向に 白なら移動 / 黒なら (K - 1, K - 1) ã§å¡—ã‚Šã¤ã¶ã—è¿½åŠ 
    // 2. 横方向に移動
    // 3. 縦方向に移動
    vector cost(R, vector(C, array{INT_MAX, 0, 0}));
    vector<pair<int, int>> q1, q2;
    auto push = [&](vector<pair<int, int>>& q, int r, int c, int x, int y, int z) -> void {
        if(r < 0 || r >= R || c < 0 || c >= C) return;
        if(cost[r][c][0] <= x) return;
        cost[r][c] = {x, y, z};
        q.emplace_back(r, c);
    };
    auto push2 = [&](int r, int c, int x) -> void {
        if(r < 0 || r >= R || c < 0 || c >= C) return;
        if(A[r][c]) push(q2, r, c, x + 1, K, K);
        else push(q1, r, c, x, 0, 0);
    };
    push(q1, Sr, Sc, 0, 0, 0);

    while(q1.size()) {
        // 横方向に移動
        for(int i = 0; i < q1.size(); i++) {
            const auto [r, c] = q1[i];
            const auto [x, y, z] = cost[r][c];
            if(z == 0) continue;
            push(q1, r, c - 1, x, y, z + 1);
            push(q1, r, c + 1, x, y, z + 1);
        }
        // 縦方向に移動
        for(int i = 0; i < q1.size(); i++) {
            const auto [r, c] = q1[i];
            const auto [x, y, z] = cost[r][c];
            if(y == 0) continue;
            push(q1, r - 1, c, x, y + 1, z);
            push(q1, r + 1, c, x, y + 1, z);
        }
        // BFS
        for(int i = 0; i < q1.size(); i++) {
            const auto [r, c] = q1[i];
            const auto [x, y, z] = cost[r][c];
            push2(r - 1, c, x);
            push2(r + 1, c, x);
            push2(r, c - 1, x);
            push2(r, c + 1, x);
        }
        swap(q1, q2);
        q2.clear();
    }

    cout << cost[Gr][Gc][0] << endl;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:43:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |         for(int i = 0; i < q1.size(); i++) {
      |                        ~~^~~~~~~~~~~
Main.cpp:51:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         for(int i = 0; i < q1.size(); i++) {
      |                        ~~^~~~~~~~~~~
Main.cpp:59:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         for(int i = 0; i < q1.size(); i++) {
      |                        ~~^~~~~~~~~~~

• 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