Hypyt

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

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

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

bool *checked; // index is y * width + x
int *depths; // normalRows, normalColumns, reverseRows, reverseColumns are backed by this

int *normalRows;
int *normalColumns;
int *reverseRows;
int *reverseColumns;

#define iter(vec, it) for (auto it = vec.begin(); it != vec.end(); it++)

template <bool Normal, bool Rows, bool Cols>
int layer(vector<pi>& 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;                


    if constexpr (Rows) {
        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 (pos.first == target.first) return 1;

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

    if constexpr (Rows) {
        for (int x : rows[pos.second]) {
            // if constexpr (Normal) {
            //     if (x == target.first) return 2;
            // }
            next.push_back({ x, pos.second });
        }
    }

    if constexpr (Cols) {
        for (int y : columns[pos.first]) {
            // if (y == target.second) return 2;
            next.push_back({ pos.first, y });
        }
    }

    return 0;
}

int search(pi start, pi end, int width, int height) {
    if (start.first == end.first && start.second == end.second) return 0;
    if (start.first == end.first || start.second == end.second) return 1;
    memset(static_cast<void*>(depths), 0, 2 * (height + width) * sizeof(int));

    normalRows = depths;
    normalColumns = depths + height;
    reverseRows = depths + height + width;
    reverseColumns = depths + height + width + height;

    int type = 0;
    int depth = 0;
    vector<pi> normalPositions{ start };
    vector<pi> reversePositions{ end };

    while (normalPositions.size() || reversePositions.size()) {
        vector<pi> nextNormalPositions;

        for (pi pos : normalPositions) {
            int rev = 
                type == 0 ?
                layer<true, true, true>(nextNormalPositions, depth + 1, pos, end)
                : (
                    type == 1 ?
                    layer<true, true, false>(nextNormalPositions, depth + 1, pos, end)
                    :
                    layer<true, false, true>(nextNormalPositions, depth + 1, pos, end)
                  );

            if (rev) return depth + rev - 1;
        }

        vector<pi> nextReversePositions;

        for (pi pos : reversePositions) {
            int rev = 
                type == 0 ?
                layer<true, true, true>(nextReversePositions, depth + 1, pos, start)
                : (
                    type == 1 ?
                    layer<true, false, true>(nextReversePositions, depth + 1, pos, start)
                    :
                    layer<true, true, false>(nextReversePositions, depth + 1, pos, start)
                  );

            if (rev) return depth + rev;
        }

        type = type == 1 ? 2 : 1;
        normalPositions = nextNormalPositions;
        reversePositions = nextReversePositions;
        depth++;
    }
    return -1;
}

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

    rows = new vector<int>[height];
    columns = new vector<int>[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);
            }
        }
    }

    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}});
    }

    depths = new int[2 * (height + width)];

    for (auto [start, end] : queries) {
        cout << search(start, end, width, height) << endl;
    }
}

Test 1 (public)

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 3

Group: 1, 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 4

Group: 1, 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 5

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 6

Group: 2, 5

Verdict: WRONG ANSWER

Test 7

Group: 2, 5

Verdict: WRONG ANSWER

Test 8

Group: 2, 5

Verdict: WRONG ANSWER

Test 9

Group: 3, 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 10

Group: 3, 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 11

Group: 3, 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 12

Group: 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 14

Group: 4, 5

Verdict: TIME LIMIT EXCEEDED

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: 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: TIME LIMIT EXCEEDED

Test 27

Group: 5

Verdict: ACCEPTED