Submission #990899

#	Time	Username	Problem	Language	Result	Execution time	Memory
990899		tincamatei	Maze (JOI23_ho_t3)	C++17	0 / 100	2067 ms	5460 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};

struct Matrix {
    int R, C, N;
    std::vector<std::string> matr;
    std::vector<int> dist;

    explicit Matrix(int _R, int _C, int _N): R(_R), C(_C), N(_N) {
        matr.resize(_R);
        dist.resize(R * C, R * C + 1);
    }

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

    int coord_to_index(int l, int c) {
        return l * C + c;
    }

    std::vector<std::tuple<int, int, int>> create_adjacency_list(int l, int c) {
        std::vector<std::tuple<int, int, int>> adj;

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

            if (in_matrix(ln, cn) && matr[ln][cn] == '.')
                adj.push_back({ln, cn, 0});
        }

        for (int ln = l - N; ln <= l + N; ln++)
            for (int cn = c - N; cn <= c + N; cn++) {
                if ((std::abs(l - ln) != N || std::abs(c - cn) != N) && in_matrix(ln, cn) &&
                        (ln != l || cn != c)) {
                    adj.push_back({ln, cn, 1});
                }
            }

        return adj;
    }

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

        while (!q.empty()) {
            int l = q.front().first;
            int c = q.front().second;
            int node = coord_to_index(l, c);

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

            q.pop_front();

            auto adj = create_adjacency_list(l, c);

            for (auto it: adj) {
                auto [ln, cn, cost] = it;
                int node_to = coord_to_index(ln, cn);
                
                std::cerr << l << " " << c << " -> " << ln << " " << cn << ": " << cost << "\n";

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

                    if (cost == 0)
                        q.push_front({ln, cn});
                    else
                        q.push_back({ln, cn});
                }
            }
        }
        
        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;
}

• 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