Hypyt

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, q;
    if (!(cin >> n >> m >> q)) return 0;
    vector<string> g(n);
    for (int i = 0; i < n; ++i) cin >> g[i];

    int N = n + m; // solmujen lukumäärä (1..n = rivit, n+1..n+m = sarakkeet)
    vector<vector<int>> adj(N+1);
    // lisää reuna rivin r (1..n) ja sarakkeen (n+c)
    for (int r = 1; r <= n; ++r) {
        for (int c = 1; c <= m; ++c) {
            if (g[r-1][c-1] == '.') {
                int u = r;
                int v = n + c;
                adj[u].push_back(v);
                adj[v].push_back(u);
            }
        }
    }

    const int INF = 1e9;
    // etäisyysmatriisi dist[u][v] solmu-etäisyyksille
    vector<vector<int>> dist(N+1, vector<int>(N+1, INF));

    // BFS kustakin solmusta
    for (int s = 1; s <= N; ++s) {
        deque<int> dq;
        dist[s][s] = 0;
        dq.push_back(s);
        while (!dq.empty()) {
            int u = dq.front(); dq.pop_front();
            for (int v : adj[u]) {
                if (dist[s][v] == INF) {
                    dist[s][v] = dist[s][u] + 1;
                    dq.push_back(v);
                }
            }
        }
    }

    // käsittele kyselyt
    for (int i = 0; i < q; ++i) {
        int y1, x1, y2, x2;
        cin >> y1 >> x1 >> y2 >> x2;
        if (y1 == y2 && x1 == x2) {
            cout << 0 << '\n';
            continue;
        }
        int a1 = y1;
        int a2 = n + x1;
        int b1 = y2;
        int b2 = n + x2;
        int best = INF;
        // minimietäisyys minkä tahansa päätepisteparin välillä
        best = min(best, dist[a1][b1]);
        best = min(best, dist[a1][b2]);
        best = min(best, dist[a2][b1]);
        best = min(best, dist[a2][b2]);
        if (best >= INF) cout << -1 << '\n';
        else cout << (best + 1) << '\n';
    }
    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