Hypyt

#include <algorithm>
#include <cstring>
#include <iostream>
#include <utility>
#include <vector>
 
using namespace std;
using pi = pair<int, int>;
 
vector<int> *rows;
vector<int> *columns;
 
int *reverseRows;
int *reverseColumns;
 
int *checkedRows;
int *checkedColumns;
 
#define Rows                                                            \
for (int i : rows[pos.second]) {                                        \
    int found = depths[pos.second][i];                                  \
    if (found <= depth + 1) continue;                                   \
                                                                        \
    int ret = find<false>(depths, depth + 1, { i, pos.second }, min);   \
    if (ret) return ret - 1;                                            \
}
 
#define Columns                                                         \
for (int i : columns[pos.first]) {                                      \
    int found = depths[i][pos.first];                                   \
    if (found <= depth + 1) continue;                                   \
                                                                        \
    int ret = find<true>(depths, depth + 1, { pos.first, i }, min);     \
    if (ret) return ret - 1;                                            \
}
 
template<bool Row>
int find(int **depths, int depth, pi pos, int *min) {
    depths[pos.second][pos.first] = depth;
 
    if (depth + 1 >= *min) return depth + 2 - *min;
    if (depth > checkedRows[pos.second]) return depth - checkedRows[pos.second];
    checkedRows[pos.second] = depth + 1;

    if (depth > checkedColumns[pos.first]) return depth - checkedColumns[pos.first];
    checkedColumns[pos.first] = depth + 1;
 
    int revRow = reverseRows[pos.second];
    int revCol = reverseColumns[pos.first];

    if (revRow) {
        if (revCol && revCol < revRow) {
            *min = depth + revCol - 1;
            return revCol - 1;
        } else {
            *min = depth + revRow - 1;
            return revRow - 1;
        }
    } else if (revCol) {
        *min = depth + revCol - 1;
        return revCol - 1;
    }
 
    if constexpr (Row) {
        Rows
        Columns
    } else {
        Columns
        Rows
    }
 
    return false;
}
 
void createReverse(pi pos, int depth, int max) {
#define set(x) if (x == 0 || depth < x) { \
    x = depth;  \
}

    set(reverseRows[pos.second])
    set(reverseColumns[pos.first])
 
    if (depth >= max) return;
 
    for (int i : rows[pos.second]) {
        createReverse({ i, pos.second }, depth + 1, max);
    }
 
    for (int i : columns[pos.first]) {
        createReverse({ pos.first, i }, depth + 1, max);
    }
}

int minGuh(int x, int y) {
    int revRow = reverseRows[y];
    int revCol = reverseColumns[x];
 
    if (revRow) {
        if (revCol && revCol < revRow) {
            return revCol;
        } else {
            return revRow;
        }
    } else if (revCol) {
        return revCol;
    }

    return 0;
}
 
int getDepth(pi start, pi end, int height, int width, int **depths) {
    if (start.first == end.first && start.second == end.second) return 0;
 
    for (int i = 0; i < height; i++) {
        memset((void*)(depths[i]), 127, width * sizeof(int));
        // sort(rows[i].begin(), rows[i].end(), [end](int i1, int i2) -> bool { return abs(i1 - end.first) < abs(i2 - end.first); });
    }

    // for (int i = 0; i < width; i++) {
    //     sort(columns[i].begin(), columns[i].end(), [end](int i1, int i2) -> bool { return abs(i1 - end.second) < abs(i2 - end.second); });
    // }

 
    memset((void*)reverseRows, 0, height * sizeof(int));
    memset((void*)reverseColumns, 0, width * sizeof(int));
    memset((void*)checkedRows, 127, height * sizeof(int));
    memset((void*)checkedColumns, 127, width * sizeof(int));
 
    createReverse(end, 1, 3);

    // cout << "------" << endl;
    // for (int y = 0; y < height; y++) {
    //     for (int x = 0; x < width; x++) {
    //         if (x == end.first && y == end.second)
    //             cout << "e";
    //         else if (x == start.first && y == start.second)
    //             cout << "s";
    //         else
    //             cout << minGuh(x, y);
    //
    // #define findSus(list, num) (find(list.begin(), list.end(), num) != list.end())
    //         if (findSus(columns[x], y)) cout << "#";
    //         else cout << " ";
    //
    //         cout << " ";
    //     }
    //
    //     cout << endl;
    //     cout << endl;
    // }
    // cout << "------" << endl;
    //
 
    int min = 42069;
    find<true>(depths, 1, start, &min);
 
    if (min == 42069) return -1;
    return min;
}
 
int main(int argc, 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);
            }
        }
    }
 
    reverseRows = new int[height];
    reverseColumns = new int[width];
    checkedRows = new int[height];
    checkedColumns = new int[width];
 
    int **depths = new int*[height];
 
    for (int i = 0; i < height; i++) depths[i] = new int[width];
 
    for (int i = 0; i < count; i++) {
        int y1, x1, y2, x2; cin >> y1 >> x1 >> y2 >> x2;
 
        pi start{ x1 - 1, y1 - 1 };
        pi end{ x2 - 1, y2 - 1 };
 
        int min = getDepth(start, end, height, width, depths);
        cout << min << 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: WRONG ANSWER

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

Test 25

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 26

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 27

Group: 5

Verdict: ACCEPTED