Hypyt

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int n, m, Q;

struct coord {
    int y;
    int x;
};

vector<vector<char>> t;
vector<vector<int>> dist;
vector<vector<coord>> prevv;

void calculateDist(int y, int x) {
    for (int i = 0; i < n; i++) {
        if (t[i][x] == '*') continue;
        if (dist[y][x] + 1 < dist[i][x]) {
            dist[i][x] = dist[y][x] + 1;
            prevv[i][x] = {y, x};
            calculateDist(i, x);
        }
    }
    for (int j = 0; j < m; j++) {
        if (t[y][j] == '*') continue;
        if (dist[y][x] + 1 < dist[y][j]) {
            dist[y][j] = dist[y][x] + 1;
            prevv[y][j] = {y, x};
            calculateDist(y, j);
        }
    }
}

int main() {
    cin >> n >> m >> Q;
    t.resize(n, vector<char> (m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> t[i][j];
        }
    }
    vector<vector<vector<int>>> allDist(n, vector<vector<int>> (n, vector<int> (m)));
    vector<vector<vector<coord>>> allPrev(n, vector<vector<coord>> (n, vector<coord> (m)));
    for (int y = 0; y < n; y++) {
        dist.resize(n, vector<int> (m));
        prevv.resize(n, vector<coord> (m));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                dist[i][j] = 1e9;
            }
        }
        for (int j = 0; j < m; j++) {
            if (t[y][j] != '*') {
                dist[y][j] = 0;
                prevv[y][j] = {-1, -1};
                calculateDist(y, j);
                break;
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                allDist[y][i][j] = dist[i][j];
                allPrev[y][i][j] = prevv[i][j];
            }
        }
    }
    for (int q = 0; q < Q; q++) {
        int y1, x1;
        cin >> y1 >> x1;
        y1--; x1--;
        int y2, x2;
        cin >> y2 >> x2;
        y2--; x2--;
        if (y1 == y2 && x1 == x2) {
            cout << 0 << '\n';
            continue;
        }
        int ans = allDist[y1][y2][x2];
        if (ans == 1e9) {
            cout << -1 << '\n';
            continue;
        }
        int y = y2;
        int x = x2;
        while (true) {
            auto p = allPrev[y1][y][x];
            if (p.y == -1) break;
            y = p.y;
            x = p.x;
        }
        if (x == x1) {
            cout << ans << '\n';
        } else {
            cout << ans + 1 << '\n';
        }
    }
}

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

Test 7

Group: 2, 5

Verdict: TIME LIMIT EXCEEDED

Test 8

Group: 2, 5

Verdict: TIME LIMIT EXCEEDED

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: WRONG ANSWER

Test 24

Group: 5

Verdict: ACCEPTED

Test 25

Group: 5

Verdict: WRONG ANSWER

Test 26

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 27

Group: 5

Verdict: ACCEPTED