Hypyt

#include<bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define fi first
#define se second
#define pii pair<int,int>
using ll = long long;

char r[251][251];

vector<int> adj[501];

int vis[501]; // solmut
int dist[251][251]; // ruudut

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m, q;
    cin >> n >> m >> q;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> r[i][j];
        }
    }

    // rows = 1...n, cols = n+1...n+m
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (r[i][j] == '*') continue;
            adj[i].push_back(n+j);
            adj[n+j].push_back(i);
        }
    }
    
    

    map<pii, vector<pair<pii,int>>> w;
    for (int i = 1; i <= q; i++) {
        int y1, x1, y2, x2;
        cin >> y1 >> x1 >> y2 >> x2;
        w[{y1,x1}].push_back({{y2,x2}, i});
    }

    vector<pii> ans;
    for (auto p : w) {
 
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                dist[i][j] = 1e9;
            }
        }
        for (int i = 1; i <= n+m; i++) vis[i] = false;

        pii a = p.fi;
        queue<pair<int,pii>> bfs; // solmu, ruutu
        bfs.push({a.fi, a});
        bfs.push({n+a.se, a});
        vis[a.fi] = vis[n+a.se] = true;
        dist[a.fi][a.se] = 0;
        while (!bfs.empty()) {
            // s = solmu, c = ruutu {y, x}
            auto [s, c] = bfs.front(); bfs.pop();
            for (int u : adj[s]) {

                if (vis[u] == n) continue;
                vis[u]++;
                
                pii t;
                if (u <= n) t = {u, c.se}; // col --> row
                else t = {c.fi, u-n}; // row --> col

                dist[t.fi][t.se] = min(dist[t.fi][t.se], dist[c.fi][c.se] + 1);
                bfs.push({u, t});

            }
        }

        for (auto u : p.se) {
            ans.push_back({u.se, dist[u.fi.fi][u.fi.se] == 1e9 ? -1 : dist[u.fi.fi][u.fi.se]});
        }

        // cout << a.fi << " " << a.se << ":\n";
        // for (int i = 1; i <= n; i++) {
        //     for (int j = 1; j <= m; j++) {
        //         if (r[i][j] == '.') cout << dist[i][j];
        //         else cout << '-';
        //     }
        //     cout << "\n";
        // }
        // cout << "\n\n";
 
    }
 
 
    sort(all(ans));
 
    for (auto u : ans) cout << u.se << "\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: 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: WRONG ANSWER

Test 10

Group: 3, 4, 5

Verdict: WRONG ANSWER

Test 11

Group: 3, 4, 5

Verdict: WRONG ANSWER

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

Test 27

Group: 5

Verdict: ACCEPTED