Hypyt

#include <bits/stdc++.h>

using namespace std;

map<int, vector<int>> mpRows;
map<int, vector<int>> mpColumns;

int bfs(int y1, int x1, int y2, int x2) {
    if (y1 == y2 && x1 == x2) {
        return 0;
    }

    set<int> rows;
    set<int> columns;
    queue<pair<pair<int, char>, int>> q;
    q.push({{y1, 'r'}, 0});
    q.push({{x1, 'c'}, 0});

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

        q.pop();

        if (op == 'r') {
            if (x == y2) {
                return price + 1;
            }
            for (int c : mpRows[x]) {
                if (!columns.contains(c)) {
                    q.push({{c, 'c'}, price + 1});
                }
                columns.insert(c);
            }
        } else {
            if (x == x2) {
                return price + 1;
            }
            for (int r : mpColumns[x]) {
                if (!rows.contains(r)) {
                    q.push({{r, 'r'}, price + 1});
                }
                rows.insert(r);
            }
        }
    }

    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];
            if (v[i][j] == '.') {
                mpRows[i].push_back(j);
                mpColumns[j].push_back(i);
            }
        }
    }

    while (q--) {
        int y1, x1, y2, x2;
        cin >> y1 >> x1 >> y2 >> x2;
        y1--;
        x1--;
        y2--;
        x2--;
        cout << bfs(y1, x1, y2, x2) << '\n';
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // cout << fixed << setprecision(6) << endl;

    int t = 1;
    // cin >> t;
    while (t--) {
        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