Hypyt

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

using namespace std;

const int INF = 1e9;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

    vector<string> grid(n);
    int num_nodes = n + m;
    vector<vector<int>> adj(num_nodes);

    for (int r = 0; r < n; ++r) {
        cin >> grid[r];
        for (int c = 0; c < m; ++c) {
            if (grid[r][c] == '.') {
                int u = r;
                int v = n + c;
                adj[u].push_back(v);
                adj[v].push_back(u);
            }
        }
    }

    vector<vector<int>> dist(num_nodes, vector<int>(num_nodes, INF));

    for (int start_node = 0; start_node < num_nodes; ++start_node) {
        if (adj[start_node].empty()) {
            continue;
        }

        dist[start_node][start_node] = 0;
        queue<int> q_bfs;
        q_bfs.push(start_node);

        while (!q_bfs.empty()) {
            int u = q_bfs.front();
            q_bfs.pop();

            for (int v : adj[u]) {
                if (dist[start_node][v] == INF) {
                    dist[start_node][v] = dist[start_node][u] + 1;
                    q_bfs.push(v);
                }
            }
        }
    }
    
    for (int i = 0; i < q; ++i) {
        int y1, x1, y2, x2;
        cin >> y1 >> x1 >> y2 >> x2;

        int r1 = y1 - 1, c1 = x1 - 1;
        int r2 = y2 - 1, c2 = x2 - 1;

        if (r1 == r2 && c1 == c2) {
            cout << "0\n";
            continue;
        }

        int u1 = r1, v1 = n + c1; 
        int u2 = r2, v2 = n + c2; 

        int d_r = min(dist[u1][u2], dist[v1][u2]);
        
        int d_c = min(dist[u1][v2], dist[v1][v2]);

        int ans = INF;

        if (d_r != INF) {
            ans = min(ans, d_r + 1);
        }
        if (d_c != INF) {
            ans = min(ans, d_c + 1);
        }
        
        if (d_c == d_r + 1) {
            ans = min(ans, d_c);
        }
        
        if (d_r == d_c + 1) {
            ans = min(ans, d_r);
        }

        if (ans == INF) {
            cout << "-1\n";
        } else {
            cout << ans << "\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