Hypyt

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

using namespace std;
using pi = pair<int, int>;

vector<int> *rows;
vector<int> *columns;

int width;
int height;

char *depths;
bool *dots;

#define INDEX(x, y) (y * width + x)

char *normalRows;
char *normalColumns;
char *reverseRows;
char *reverseColumns;

inline bool fastCorner(pi start, pi end) {
    if (dots[INDEX(start.first, end.second)] ||
            dots[INDEX(end.first, start.second)]) return true;
    return false;
}

template <bool First, bool Normal, bool Rows, bool Cols>
int layer(vector<pair<pi, int>>& next, int depth, pi pos, pi target) {

#define CHECK(norm, reverse, index)         \
            if (norm[index]) return 0;      \
            norm[index] = depth;            \
                                            \
            int rev = reverse[index];       \
            if (rev) return rev - 1;                

    if constexpr (First)
        if (fastCorner(pos, target)) return 2;

    if constexpr (Rows) {
        if constexpr (First)
            if (pos.second == target.second) return 1;

        if constexpr (Normal) {
            CHECK(normalRows, reverseRows, pos.second)
        } else {
            CHECK(reverseRows, normalRows, pos.second)
        }
    }

    if constexpr (Cols) {
        if constexpr (First)
            if (pos.first == target.first) return 1;

        if constexpr (Normal) {
            CHECK(normalColumns, reverseColumns, pos.first)
        } else {
            CHECK(reverseColumns, normalColumns, pos.first)
        }
    }

    if constexpr (Rows) {
        std::vector<int> *vec = rows + pos.second;
        // for (int x : rows[pos.second]) {
        for (auto it = vec->begin(); it != vec->end(); it++) {
            int x = *it;
            if (x == pos.first) continue;
            if (x == target.first) return 1;

            if constexpr (Normal) {
                int rev = reverseColumns[x];
                if (rev) return rev;
            } else {
                int rev = normalColumns[x];
                if (rev) return rev;
            }

            pi nextPos = { x, pos.second };
            if (fastCorner(nextPos, target)) return 2;

            next.push_back({ nextPos, 2 });
        }
    }

    if constexpr (Cols) {
        std::vector<int> *vec = columns + pos.first;
        // for (int y : columns[pos.first]) {
        for (auto it = vec->begin(); it != vec->end(); it++) {
            int y = *it;
            if (y == pos.second) continue;
            if (y == target.second) return 1;

            if constexpr (Normal) {
                int rev = reverseRows[y];
                if (rev) return rev;
            } else {
                int rev = normalRows[y];
                if (rev) return rev;
            }

            pi nextPos{ pos.first, y };
            if (fastCorner(nextPos, target)) return 2;

            next.push_back({ nextPos, 1 });
        }
    }

    return 0;
}


int search(pi start, pi end) {
    if (start.first == end.first && start.second == end.second) return 0;
    if (start.first == end.first || start.second == end.second) return 1;
    if (fastCorner(start, end)) return 2;

    memset(static_cast<void*>(depths), 0, 2 * (height + width) * sizeof(char));

    int depth = 1;
    vector<pair<pi, int>> normalPositions{ { start, 0 } };
    vector<pair<pi, int>> reversePositions{ { end, 0 } };

    while (normalPositions.size() && reversePositions.size()) {
        // cout << "depth " << depth << endl;
        vector<pair<pi, int>> nextNormalPositions;
        nextNormalPositions.reserve(normalPositions.size() * 4);
        
        // for (auto [pos, type] : normalPositions) {
        for (auto it = normalPositions.begin(); it != normalPositions.end(); it++) {
            int rev = 
                it->second == 0 ?
                layer<true, true, true, true>(nextNormalPositions, depth, it->first, end)
                : (
                    it->second == 1 ?
                    layer<false, true, true, false>(nextNormalPositions, depth, it->first, end)
                    :
                    layer<false, true, false, true>(nextNormalPositions, depth, it->first, end)
                  );

            if (rev) return depth + rev;
        }

        // cout << "norm: " << endl;
        // for (auto [pos, type] : nextNormalPositions) {
        //     cout << "  (" << pos.first << ", " << pos.second << ") " << type << endl;
        // }
        

        vector<pair<pi, int>> nextReversePositions;
        nextReversePositions.reserve(reversePositions.size() * 4);

        // for (auto [pos, type] : reversePositions) {
        for (auto it = reversePositions.begin(); it != reversePositions.end(); it++) {
            int rev = 
                it->second == 0 ?
                layer<true, false, true, true>(nextReversePositions, depth, it->first, start)
                : (
                    it->second == 1 ?
                    layer<false, false, true, false>(nextReversePositions, depth, it->first, start)
                    :
                    layer<false, false, false, true>(nextReversePositions, depth, it->first, start)
                  );

            if (rev) return depth + rev;
        }

        // cout << "reverse: " << endl;
        // for (auto [pos, type] : nextReversePositions) {
        //     cout << "  (" << pos.first << ", " << pos.second << ") " << type << endl;
        // }

        normalPositions = std::move(nextNormalPositions);
        reversePositions = std::move(nextReversePositions);
        depth++;
    }
    return -1;
}

// #define DEBUG

#ifdef DEBUG
uint64_t rdtsc(){
    unsigned long lo,hi;
    __asm__ __volatile__ ("rdtsc" : "=a" (lo), "=d" (hi));
    return ((uint64_t)hi << 32) | lo;
}
#endif // DEBUG

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

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

    dots = new bool[height * width];
    memset(static_cast<void*>(dots), 0, height * width);

    for (int y = 0; y < height; y++) {
        for (int x = 0; x < width; x++) {
            char c; cin >> c;

            if (c == '.') {
                dots[INDEX(x, y)] = true;
                rows[y].push_back(x);
                columns[x].push_back(y);
            }
        }
    }

    vector<pair<pi, pi>> queries;

    depths = new char[2 * (height + width)];
    normalRows = depths;
    normalColumns = depths + height;
    reverseRows = depths + height + width;
    reverseColumns = depths + height + width + height;

#ifdef DEBUG
    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}});
    }

    uint64_t cyclesStart = rdtsc();
    auto startTime = chrono::high_resolution_clock::now();
    for (auto [start, end] : queries) {
        int ans = search(start, end);
        cout << ans << '\n';
    }
    auto endTime = chrono::high_resolution_clock::now();
    cout << "time: " << endTime - startTime << '\n';
    uint64_t cyclesEnd = rdtsc();

    cout << "cycles " << cyclesEnd - cyclesStart << endl;
#else
    for (int i = 0; i < count; i++) {
        int y1, x1, y2, x2; cin >> y1 >> x1 >> y2 >> x2;
        cout << search({x1 - 1, y1 - 1}, {x2 - 1, y2 - 1}) << '\n';
    }
#endif // DEBUG
}

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: ACCEPTED

Test 16

Group: 5

Verdict: ACCEPTED

Test 17

Group: 5

Verdict: ACCEPTED

Test 18

Group: 5

Verdict: ACCEPTED

Test 19

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 20

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 21

Group: 5

Verdict: TIME LIMIT EXCEEDED

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: ACCEPTED

Test 27

Group: 5

Verdict: ACCEPTED