Submission #990964

#	Time	Username	Problem	Language	Result	Execution time	Memory
990964		tincamatei	Maze (JOI23_ho_t3)	C++14	100 / 100	1151 ms	279840 KiB

Main

// If this is correct, God forgive my soul for trying to code the legit solution.
#include <bits/stdc++.h>

//int dl[] = {1, 0, -1, 0};
//int dc[] = {0, 1,  0,-1};

int size_diff[5] = {4, 2, 2, 2, 2};
std::vector<int> dl[5] = {
    {0, 1, 0, -1},
    {1, 0},  // goes towards DR
    {1, 0},  // DL
    {-1, 0}, // UL
    {-1, 0}   // UR
};

std::vector<int> dc[5] = {
    {1, 0, -1, 0},
    {0, 1},
    {0,-1},
    {0,-1},
    {0, 1}
};

struct Matrix {
    int R, C, N;

    int B;

    std::vector<int> corner_dl;
    std::vector<int> corner_dc;
    std::vector<int> new_type_d;

    std::vector<std::string> matr;
    std::vector<int> dist;

    int size;
    std::tuple<int, int, int, int> buffer[16];

    explicit Matrix(int _R, int _C, int _N): R(_R), C(_C), N(_N) {
        matr.resize(_R);
        dist.resize(R * C * 5, R * C * 5 + 1);
        B = 2 * N - 1;

        //            UL,                      DL                     DR                   UR
        corner_dl  = {-N,     -N + 1, -N + 1,  N - 1,  N - 1, N,      N,     N - 1, N - 1, -N,   -N + 1, -N + 1};
        corner_dc  = {-N + 1, -N + 1, -N,     -N,     -N + 1, -N + 1, N - 1, N - 1, N,     N - 1, N - 1,  N};
        new_type_d = { 1,      1,      1,      4,      4,      4,     3,     3,     3,     2,     2,      2};
    }

    bool in_matrix(int l, int c) {
        return 0 <= l && l < R && 0 <= c && c < C;
    }

    int coord_to_index(int l, int c, int type = 0) {
        return type * R * C + l * C + c;
    }

    void snap_to_matrix(int& ln, int& cn) {
        ln = std::max(0, std::min(ln, R - 1));
        cn = std::max(0, std::min(cn, C - 1));
    }

    int in_block(int x) {
        if (x < 0) {
            return (x - B + 1) / B;
        }
        return x / B;
    }

    std::pair<int, int> in_block(int l, int c) {
        return {in_block(l), in_block(c)};
    }

    void create_adjacency_list(int l, int c, int type) {
        size = 0;

        if (type == 0) {
            for (int d = 0; d < 4; d++) {
                int ln = l + dl[0][d];
                int cn = c + dc[0][d];

                if (in_matrix(ln, cn) && matr[ln][cn] == '.')
                    buffer[size++] = {ln, cn, 0, 0};
            }

            for (int d = 0; d < corner_dl.size(); d++) {
                int ln = l + corner_dl[d];
                int cn = c + corner_dc[d];

                int lnn = ln;
                int cnn = cn;

                snap_to_matrix(lnn, cnn);
                if (in_block(ln, cn) == in_block(lnn, cnn) && std::make_pair(l, c) != std::make_pair(ln, cn))
                    buffer[size++] = {lnn, cnn, new_type_d[d], 1};
            }
        } else {
            buffer[size++] = {l, c, 0, 0};

            for (int d = 0; d < 2; d++) {
                int ln = l + dl[type][d];
                int cn = c + dc[type][d];

                if (in_matrix(ln, cn) && in_block(l, c) == in_block(ln, cn))
                    buffer[size++] = {ln, cn, type, 0};
            }
        }
    }

    int run_bfs(int Sl, int Sc, int Dl, int Dc) {
        std::deque<std::tuple<int, int, int>> q;
        dist[coord_to_index(Sl, Sc)] = 0;
        q.push_back({Sl, Sc, 0});

        while (!q.empty()) {
            auto [l, c, type] = q.front();
            int node = coord_to_index(l, c, type);

            //std::cerr << l << " " << c << " " << type << " -> " << dist[coord_to_index(l, c, type)] << "(" << node << ")" << "\n";

            if (l == Dl && c == Dc)
                return dist[node];

            q.pop_front();

            create_adjacency_list(l, c, type);

            for (int i = 0; i < size; i++) {
                auto [ln, cn, new_type, cost] = buffer[i];
                int node_to = coord_to_index(ln, cn, new_type);
            
                //std::cerr << "   -> " << ln << " " << cn << " " << new_type << "(" << node_to << ")" << "\n";

                if (dist[node] + cost < dist[node_to]) {
                    dist[node_to] = dist[node] + cost;

                    if (cost == 0)
                        q.push_front({ln, cn, new_type});
                    else
                        q.push_back({ln, cn, new_type});
                }
            }
        }
        
        return dist[coord_to_index(Dl, Dc)];
    }
};

int main() {
    std::cin.tie(NULL);
    std::iostream::sync_with_stdio(false);

    int R, C, N;

    std::cin >> R >> C >> N;

    int Sl, Sc, Dl, Dc;
    std::cin >> Sl >> Sc >> Dl >> Dc;

    Sl--; Sc--; Dl--; Dc--;

    Matrix M(R, C, N);

    for (int i = 0; i < R; i++)
        std::cin >> M.matr[i];

    std::cout << M.run_bfs(Sl, Sc, Dl, Dc);
    
    return 0;
}

Compilation message (stderr)

Main.cpp: In member function 'void Matrix::create_adjacency_list(int, int, int)':
Main.cpp:86:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |             for (int d = 0; d < corner_dl.size(); d++) {
      |                             ~~^~~~~~~~~~~~~~~~~~
Main.cpp: In member function 'int Matrix::run_bfs(int, int, int, int)':
Main.cpp:116:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  116 |             auto [l, c, type] = q.front();
      |                  ^
Main.cpp:129:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  129 |                 auto [ln, cn, new_type, cost] = buffer[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