Hypyt

#include <iostream>
#include <vector>
#include <queue>
#include <limits>
#include <algorithm>

using namespace std;



int main() {
    ios::sync_with_stdio(false);

    int n, m, q;
    cin >> n >> m >> q;

    vector<string> grid(n);
    for (int i = 0; i < n; ++i) cin >> grid[i];

    int V = n + m;
    vector<vector<int>> adj(V);

    // bipartite graph
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (grid[i][j] == '.') 
            {
                int u = i;
                int v = n + j;
                adj[u].push_back(v);
                adj[v].push_back(u);
            }
        }
    }

    const int INF = numeric_limits<int>::max();
    vector<vector<int>> dist(V, vector<int>(V, INF));

    // bfs
    queue<int> dq;
    for (int s = 0; s < V; ++s) 
    {
        fill(dist[s].begin(), dist[s].end(), INF);
        dist[s][s] = 0;

        while (!dq.empty()) dq.pop();

        dq.push(s);

        while (!dq.empty()) 
        {
            int u = dq.front();
            dq.pop();
            for (int v : adj[u]) 
            {
                if (dist[s][v] == INF) {
                    dist[s][v] = dist[s][u] + 1;
                    dq.push(v); 
                }
            }
        }
    }

    for (int i = 0; i < q; ++i) 
    {
        int y1, x1, y2, x2;
        cin >> y1 >> x1 >> y2 >> x2;
        y1--; x1--; y2--; x2--;

        if (y1 == y2 && x1 == x2) {
            cout << 0 << '\n';
            continue;
        }

        int s_row = y1;
        int s_col = n + x1;
        int t_row = y2;
        int t_col = n + x2;

        int best = INF;
        best = min(best, dist[s_row][t_row]);
        best = min(best, dist[s_row][t_col]);
        best = min(best, dist[s_col][t_row]);
        best = min(best, dist[s_col][t_col]);

        if (best == INF) cout << -1 << '\n';
        else cout << (1 + best) << '\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