Hypyt

#include <bits/stdc++.h>

using namespace std;

map<pair<char, int>, vector<pair<char, int>>> G;
map<pair<char, int>, map<pair<char, int>, int>> dist;

int n, m;

void bfs(char rc, int x) {
    // Set -1 to all distances
    for (int i = 0; i < n; i++) {
        dist[{rc, x}][{'r', i}] = -1;
    }
    for (int i = 0; i < m; i++) {
        dist[{rc, x}][{'c', i}] = -1;
    }

    // Set distance to current = 0
    dist[{rc, x}][{rc, x}] = 0;
    queue<pair<char, int>> q;
    q.push({rc, x});

    while (!q.empty()) {
        pair<char, int> p = q.front();
        q.pop();
        for (pair<char, int> u : G[p]) {
            // If haven't yet been into there
            if (dist[{rc, x}][u] == -1) {
                // Set distance
                dist[{rc, x}][u] = dist[{rc, x}][p] + 1;

                // Save for checking later
                q.push(u);
            }
        }
    }
}

void solve() {
    int q;
    cin >> n >> m >> q;
    vector<vector<char>> v(n, vector<char>(m));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> v[i][j];
            if (v[i][j] == '.') {
                G[{'r', i}].push_back({'c', j});
                G[{'c', j}].push_back({'r', i});
            }
        }
    }

    // Precalculate dist
    for (int i = 0; i < n; i++) {
        bfs('r', i);
    }

    for (int i = 0; i < m; i++) {
        bfs('c', i);
    }

    while (q--) {
        int y1, x1, y2, x2;
        cin >> y1 >> x1 >> y2 >> x2;
        y1--;
        x1--;
        y2--;
        x2--;
        if (y1 == y2 && x1 == x2) {
            cout << 0 << endl;
            continue;
        }

        int ans = dist[{'c', x1}][{'r', y2}];
        ans = min(ans, dist[{'c', x1}][{'c', x2}]);
        ans = min(ans, dist[{'r', y1}][{'r', y2}]);
        ans = min(ans, dist[{'r', y1}][{'c', x2}]);

        if (ans != -1) {
            ans++;
        }
        cout << ans << endl;
    }
}

int main() {
    solve();
    return 0;
}

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

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