Hypyt

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> dist;
vector<vector<int>> G;


void bfs(int st) {
    dist[st][st] = 0;
    queue<int> q;
    q.push(st);

    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (int u : G[v]) {
            if (dist[st][u] == -1) {
                dist[st][u] = dist[st][v] + 1;
                q.push(u);
            }
        }
    }
}

void solve() {
    int n, m, q;
    cin >> n >> m >> q;
    dist.resize(n + m, vector<int>(n + m, -1));
    G.resize(n + m, vector<int>());
    vector<vector<char>> grid(n, vector<char>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
            if (grid[i][j] == '.') {
                G[i].push_back(j + n);
                G[j + n].push_back(i);
            }
        }
    }
    for (int i = 0; i < n; i++) {
        bfs(i);
    }
    for (int j = 0; j < m; j++) {
        bfs(n + j);
    }

    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[y1][y2];
        ans = min(ans, dist[y1][n + x2]);
        ans = min(ans, dist[n + x1][y2]);
        ans = min(ans, dist[n + x1][n + x2]);

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

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

Test 16

Group: 5

Verdict: ACCEPTED

Test 17

Group: 5

Verdict: ACCEPTED

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

Test 27

Group: 5

Verdict: ACCEPTED