Hypyt

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int rows, cols, queries;
    cin >> rows >> cols >> queries;

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

    int totalNodes = rows + cols;
    vector<vector<int>> graph(totalNodes);

    for (int r = 0; r < rows; ++r) {
        for (int c = 0; c < cols; ++c) {
            if (mapData[r][c] == '.') {
                int rowNode = r;
                int colNode = rows + c;
                graph[rowNode].push_back(colNode);
                graph[colNode].push_back(rowNode);
            }
        }
    }

    const int INF = 1e9;
    vector<vector<int>> dist(totalNodes, vector<int>(totalNodes, INF));

    for (int start = 0; start < totalNodes; ++start) {
        queue<int> q;
        dist[start][start] = 0;
        q.push(start);

        while (!q.empty()) {
            int node = q.front();
            q.pop();

            for (int nxt : graph[node]) {
                if (dist[start][nxt] > dist[start][node] + 1) {
                    dist[start][nxt] = dist[start][node] + 1;
                    q.push(nxt);
                }
            }
        }
    }

    while (queries--) {
        int y1, x1, y2, x2;
        cin >> y1 >> x1 >> y2 >> x2;
        --y1; --x1; --y2; --x2;

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

        int srcRow = y1;
        int srcCol = rows + x1;
        int dstRow = y2;
        int dstCol = rows + x2;

        int ans = INF;
        ans = min({ans, dist[srcRow][dstRow], dist[srcRow][dstCol],
                        dist[srcCol][dstRow], dist[srcCol][dstCol]});

        cout << (ans == INF ? -1 : ans + 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