Hypyt

#include <algorithm>
#include <cstring>
#include <iostream>
#include <map>
#include <vector>
#include <chrono>

using namespace std;

using in = int;
using pi = pair<in, in>;

vector<in> *rows;
vector<in> *columns;
bool **checked;

// These are 2 * 250 * sizeof(int) = 2000 bytes, in the reverse for each lcoation, we can cache all ~60k tries because 2̈́'000 * 60'000 = 120'000'000
int *reverseRows;
int *reverseColumns;

inline int getRev(int x, int y) {
    int revRow = reverseRows[y];
    int revCol = reverseColumns[x];

    int m = min(revRow, revCol);
    if (m < 1'000'000) return m;
    return 0;
}

template <bool Rows, bool Cols>
char find(vector<pair<pi, char>>& next, pi pos, pi end) {
    int rev = getRev(pos.first, pos.second);
    if (rev) return rev;

    if (checked[pos.second][pos.first]) return false;
    checked[pos.second][pos.first] = true;

    if constexpr (Rows) {
        for (in x : rows[pos.second]) {
            // if (x == end.first) return 2;
            if (x == pos.first) continue;

            int rev = reverseColumns[pos.first];
            if (rev < 1'000'000) return rev + 1;

            next.push_back({{ x, pos.second }, 0});
        }
    }

    if constexpr (Cols) {
        for (in y : columns[pos.first]) {
            // if (y == end.second) return 2;
            if (y == pos.second) continue;

            int rev = reverseRows[pos.second];
            if (rev < 1'000'000) return rev + 1;

            next.push_back({{ pos.first, y }, 1});
        }
    }

    return false;
}

template <bool Rows, bool Cols>
int reverse(vector<pair<pi, char>>& next, pi pos, pi start, int depth) {
    if (start.first == pos.first || start.second == pos.second) return 1;

    if (checked[pos.second][pos.first]) return 0;
    checked[pos.second][pos.first] = true;

    if constexpr (Rows) if (depth < reverseRows[pos.second]) reverseRows[pos.second] = depth;
    if constexpr (Cols) if (depth < reverseColumns[pos.first]) reverseColumns[pos.first] = depth;

    if constexpr (Rows) {
        for (in x : rows[pos.second]) {
            if (x == start.first) return 2;
            if (x == pos.first) continue;
            next.push_back({{ x, pos.second }, 0});
        }
    }

    if constexpr (Cols) {
        for (in y : columns[pos.first]) {
            if (y == start.second) return 2;
            if (y == pos.second) continue;
            next.push_back({{ pos.first, y }, 1});
        }
    }

    return 0;
}

int searchReverse(pi end, pi start, int max) {
    std::vector<pair<pi, char>> next{{end, 0}};
    int depth = 1;
    
    while (next.size() && depth <= max) {
        std::vector<pair<pi, char>> copy;
        copy.reserve(next.size() * 4);
        // cout << "dep: " << depth << endl;

        for (auto [pos, type] : next) {
            int sus = depth == 1 ? reverse<true, true>(copy, pos, start, depth) : (depth >= max ? reverse<false, false>(copy, pos, start, depth) : 
                (type == 1 ? reverse<true, false>(copy, pos, start, depth) : reverse<false, true>(copy, pos, start, depth)));
            if (sus) return depth + sus - 1;
        }

        next = copy;
        depth++;
    }

    return 0;
}

int calcReverse(pi start, pi end, int height, int width) {
    memset((void*)reverseRows, 127, height * sizeof(int));
    memset((void*)reverseColumns, 127, width * sizeof(int));

    // 1: 779 ms
    // 2: 132 ms
    // 3: 76.2 ms
    // 4: 83.0 ms
    // 5: 72.5 ms
    // 6: 72.6 ms
    // 7: 76.4 ms
    int rev = searchReverse(end, start, 3);
    return rev;
}

int search(pi start, pi end, int height, int width) {
    if (start.first == end.first && start.second == end.second) return 0;

    for (int i = 0; i < height; i++) 
        memset((void*)checked[i], 0, width);

    int rev = calcReverse(start, end, height, width);
    if (rev) return rev;

    // cout << endl;
    // for (int i = 0; i < height; i++) {
    //     for (int j = 0; j < width; j++) {
    //         int rev = min(reverseRows[i], reverseColumns[j]);
    //         cout << ((rev > 1'000'000) ? 0 : rev) << " ";
    //     }
    //     cout << endl;
    // }

    std::vector<pair<pi, char>> next{{start, 0}};
    int depth = 0;

    for (int i = 0; i < height; i++) 
        memset((void*)checked[i], 0, width);

    while (next.size()) {
        std::vector<pair<pi, char>> copy;
        copy.reserve(next.size() * 4);

        // for (pi pos : next) {
        //     int sus = find(copy, pos, end);
        //     if (sus) return depth + sus;
        // }
        //
        for (auto [pos, type] : next) {
            int sus = depth == 0 ? find<true, true>(copy, pos, end) : (type == 1 ? find<true, false>(copy, pos, end) : find<false, true>(copy, pos, end));
            if (sus) return depth + sus;
        }

        next = copy;
        depth++;
    }

    return -1;
}

int main(int argc, char *argv[]) {
    int height, width, count; cin >> height >> width >> count;

    rows = new vector<in>[height];
    columns = new vector<in>[width];

    for (int y = 0; y < height; y++) {
        for (int x = 0; x < width; x++) {
            char c; cin >> c;
            if (c == '.') {
                rows[y].push_back(x);
                columns[x].push_back(y);
            }
        }
    }

    reverseRows = new int[height];
    reverseColumns = new int[width];

    checked = new bool*[height];
    for (int i = 0; i < height; i++) checked[i] = new bool[width];

    vector<pair<pi, pi>> queries;
    
    for (int i = 0; i < count; i++) {
        int y1, x1, y2, x2; cin >> y1 >> x1 >> y2 >> x2;
        queries.push_back({{ x1 - 1, y1 - 1 }, { x2 - 1, y2 - 1 }});
    }

    map<pair<pi, pi>, int> cache;


    // auto startTime = chrono::high_resolution_clock::now();
    for (auto [start, end] : queries) {
        auto it = cache.find({start, end});
        if (it != cache.end()) {
            cout << it->second << endl;
            continue;
        }
        int sus = search(start, end, height, width);
        cache[{start, end}] = sus;
        cout << sus << endl;
    }
    // auto endTime = chrono::high_resolution_clock::now();
    //
    // cout << "time: " << endTime - startTime << endl;
}

Test 1 (public)

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 3

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 4

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 5

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 6

Group: 2, 5

Verdict: ACCEPTED

Test 7

Group: 2, 5

Verdict: ACCEPTED

Test 8

Group: 2, 5

Verdict: ACCEPTED

Test 9

Group: 3, 4, 5

Verdict: ACCEPTED

Test 10

Group: 3, 4, 5

Verdict: ACCEPTED

Test 11

Group: 3, 4, 5

Verdict: ACCEPTED

Test 12

Group: 4, 5

Verdict: ACCEPTED

Test 13

Group: 4, 5

Verdict: ACCEPTED

Test 14

Group: 4, 5

Verdict: ACCEPTED

Test 15

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 16

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 17

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 18

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 19

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 20

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 21

Group: 5

Verdict: ACCEPTED

Test 22

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 23

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 24

Group: 5

Verdict: ACCEPTED

Test 25

Group: 5

Verdict: ACCEPTED

Test 26

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 27

Group: 5

Verdict: ACCEPTED