Hypyt

#include <bits/stdc++.h>

using namespace std;

map<pair<int, int>, vector<pair<int, int>>> G;

int bfs(pair<int, int> st, pair<int, int> en) {
    set<pair<int, int>> was;
    queue<pair<pair<int, int>, int>> q;
    q.push({st, 0});
    while (!q.empty()) {
        pair<pair<int, int>, int> u = q.front();
        q.pop();
        if (u.first == en) {
            return u.second;
        }
        for (pair<int, int> v : G[u.first]) {
            if (!was.contains(v)) {
                q.push({v, u.second + 1});
                was.insert(v);
            }
        }
    }
    return -1;
}

void solve() {
    long long n, m, q;
    cin >> n >> m >> q;
    vector<vector<char>> map(n, vector<char>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (map[i][j] == '.') {
                for (int ii = i + 1; ii < n; ii++) {
                    if (map[ii][j] == '.') {
                        G[{i, j}].push_back({ii, j});
                        G[{ii, j}].push_back({i, j});
                    }
                }
                for (int jj = j + 1; jj < m; jj++) {
                    if (map[i][jj] == '.') {
                        G[{i, j}].push_back({i, jj});
                        G[{i, jj}].push_back({i, j});
                    }
                }
            }
        }
    }

    while (q--) {
        int y1, x1, y2, x2;
        cin >> y1 >> x1 >> y2 >> x2;
        y1--;
        x1--;
        y2--;
        x2--;
        cout << bfs({y1, x1}, {y2, x2}) << 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: TIME LIMIT EXCEEDED

Test 7

Group: 2, 5

Verdict: TIME LIMIT EXCEEDED

Test 8

Group: 2, 5

Verdict: TIME LIMIT EXCEEDED

Test 9

Group: 3, 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 10

Group: 3, 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 11

Group: 3, 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 12

Group: 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 14

Group: 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 16

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 17

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 18

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 19

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 20

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 21

Group: 5

Verdict: TIME LIMIT EXCEEDED

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: TIME LIMIT EXCEEDED

Test 25

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 26

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 27

Group: 5

Verdict: ACCEPTED