Hypyt

#include <bits/stdc++.h>

using namespace std;

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

int n, m;

void bfs(char rc, int x) {
    // Set -1 to all distances
    dist[{rc, x}].first.resize(n, -1); // rows
    dist[{rc, x}].second.resize(m, -1); // columns

    // Set distance to current = 0
    if (rc == 'r') {
        dist[{rc, x}].first[x] = 0;
    } else {
        dist[{rc, x}].second[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 (u.first == 'r') {
                if (dist[{rc, x}].first[u.second] == -1) {
                    // Set distance
                    if (p.first == 'r') {
                        dist[{rc, x}].first[u.second] = dist[{rc, x}].first[p.second] + 1;
                    } else {
                        dist[{rc, x}].first[u.second] = dist[{rc, x}].second[p.second] + 1;
                    }

                    // Save for checking later
                    q.push(u);
                }
            } else {
                if (dist[{rc, x}].second[u.second] == -1) {
                    // Set distance
                    if (p.first == 'r') {
                        dist[{rc, x}].second[u.second] = dist[{rc, x}].first[p.second] + 1;
                    } else {
                        dist[{rc, x}].second[u.second] = dist[{rc, x}].second[p.second] + 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}].first[y2];
        ans = min(ans, dist[{'c', x1}].second[x2]);
        ans = min(ans, dist[{'r', y1}].first[y2]);
        ans = min(ans, dist[{'r', y1}].second[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: 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: 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: ACCEPTED

Test 19

Group: 5

Verdict: ACCEPTED

Test 20

Group: 5

Verdict: ACCEPTED

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