Hypyt

#include <bits/stdc++.h>

using namespace std;

int bfs(map<pair<char, int>, vector<pair<char, int>>> &G, int y1, int x1, int y2, int x2) {
    if (y1 == y2 && x1 == x2) {
        return 0;
    }
    set<pair<char, int>> was;
    queue<pair<pair<char, int>, int>> q;
    q.push({{'r', y1}, 1});
    q.push({{'c', x1}, 1});

    while (!q.empty()) {
        pair<char, int> p = q.front().first;
        int cnt = q.front().second;
        q.pop();

        was.insert(p);

        if (p.first == 'r' && p.second == y2) {
            return cnt;
        }

        if (p.first == 'c' && p.second == x2) {
            return cnt;
        }

        for (pair<char, int> u : G[p]) {
            if (!was.count(u)) {
                q.push({u, cnt + 1});
            }
        }
    }

    return -1;
}

void solve() {
    int n, m, 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];
        }
    }
    map<pair<char, int>, vector<pair<char, int>>> G;
    for (int r = 0; r < n; r++) {
        for (int c = 0; c < m; c++) {
            if (v[r][c] == '.') {
                G[{'r', r}].push_back({'c', c});
                G[{'c', c}].push_back({'r', r});
            }
        }
    }

    while (q--) {
        int y1, x1, y2, x2;
        cin >> y1 >> x1 >> y2 >> x2;
        y1--;
        x1--;
        y2--;
        x2--;
        cout << bfs(G, y1, x1, y2, x2) << 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: 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: ACCEPTED

Test 25

Group: 5

Verdict: ACCEPTED

Test 26

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 27

Group: 5

Verdict: ACCEPTED