Hypyt

#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <unistd.h>
#include <vector>

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

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

constexpr int NOT_FOUND = 10000;

void findPath(int **path, int depth, pi pos, bool row, pi target, int *min) {
    path[pos.first][pos.second] = depth;

    int whenExact = depth - 1;
    if (whenExact >= *min) return;

    if (pos.first == target.first && pos.second == target.second) {
        *min = whenExact;
        return;
    }

    if (depth >= *min) return;
    if (pos.first == target.first || pos.second == target.second) {
        *min = depth;
        return;
    }

    if (depth + 1 >= *min) return;

    vector<int> list = row ? rows[pos.second] : columns[pos.first];
    if (list.empty()) return;

    if (row)
        sort(list.begin(), list.end(), [target](int p1, int p2) -> bool { return abs(p1 - target.first) < abs(p2 - target.first); });
    else
        sort(list.begin(), list.end(), [target](int p1, int p2) -> bool { return abs(p1 - target.second) < abs(p2 - target.second); });

    for (int i : list) {
        pi pos2;
        if (row) pos2 = { i, pos.second };
        else pos2 = { pos.first, i };

        int found = path[pos2.first][pos2.second];

        if (found <= depth + 1) continue;

        findPath(path, depth + 1, pos2, !row, target, 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);
            }
        }
    }
    
    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 } });
    }

    int **path = new int*[width];

    for (int i = 0; i < width; i++) {
        int *arr = new int[width];
        path[i] = arr;
    }

    for (auto [start, end] : queries) {
        int min = NOT_FOUND;

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

        findPath(path, 1, start, true, end, &min);
        findPath(path, 1, start, false, end, &min);

        if (min == NOT_FOUND) min = -1;

        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: 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: 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: RUNTIME ERROR

malloc(): corrupted top size

Test 23

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 24

Group: 5

Verdict: RUNTIME ERROR

malloc(): corrupted top size

Test 25

Group: 5

Verdict: ACCEPTED

Test 26

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 27

Group: 5

Verdict: TIME LIMIT EXCEEDED