Hypyt

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;

#define MOD (ll)(998244353LL) //1e9+7

int n, m;
vector<vector<bool>> a;
vector<vector<vector<pair<int, int>>>> adj;
vector<vector<vector<int>>> dst;

void fill(const int& idx, const int ix, const int iy) {
    if (ix == -1 || iy == -1) return;
    priority_queue<tuple<int, int, int, int>> q;
    q.push({0, ix, iy, idx < m ? 3 : 1});
    
    while (!q.empty()) {
        tuple<int,int,int,int> v = q.top();
        q.pop();
        if (dst[idx][get<1>(v)][get<2>(v)] != -1) continue;
        dst[idx][get<1>(v)][get<2>(v)] = -get<0>(v);

        for (int i = 0; i < 4; i++) {
            auto& p = adj[get<1>(v)][get<2>(v)][i];
            if (p.first == -1 || p.second == -1) continue;

            q.push({get<0>(v) - (i == get<3>(v) ? 0 : 1), p.first, p.second, i});
        }
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    
    int q; cin >> n >> m >> q;
    a.resize(m, vector<bool>(n));
    dst.resize(n + m, vector<vector<int>>(m, vector<int>(n, -1)));
    adj.resize(m, vector<vector<pair<int, int>>>(n, vector<pair<int, int>>(4, {-1,-1})));

    for (int y = 0; y < n; y++) {
        for (int x = 0; x < m; x++) {
            char c; cin >> c;
            a[x][y] = c == '.';
        }
    }
    
    vector<int> x_a(n,-1), x_b(n,-1), y_a(m,-1), y_b(m,-1);
    for (int y = 0; y < n; y++) {
        for (int x = 0; x < m; x++) {
            if (a[x][y]) {
                adj[x][y][0] = {x_a[y], y};
                x_a[y] = x;
            }
            if (a[m-x-1][y]) {
                adj[m-x-1][y][1] = {x_b[y], y};
                x_b[y] = m-x-1;
            }
        }
    }
    for (int x = 0; x < m; x++) {
        for (int y = 0; y < n; y++) {
            if (a[x][y]) {
                adj[x][y][2] = {x, y_a[x]};
                y_a[x] = y;
            }
            if (a[x][n-y-1]) {
                adj[x][n-y-1][3] = {x, y_b[x]};
                y_b[x] = n-y-1;
            }
        }
    }
    for (int x = 0; x < m; x++) {
        fill(x, x, y_b[x]);
    }
    for (int y = 0; y < n; y++) {
        fill(m+y, x_b[y], y);
    }
    for (int i = 0; i < q; i++) {
        int y1, x1, y2, x2; cin >> y1 >> x1 >> y2 >> x2;
        int mn = 2*m*n;
        
        for (int j = 0; j < n+m; j++) {
            int g = dst[j][x1-1][y1-1];
            int h = dst[j][x2-1][y2-1];
            int d = g + h + ((y1 != y2 || x1 != x2) ? 1 : 0);
            if (g != -1 && h != -1) mn = min(mn, d);
        }
        if (mn == 2*m*n) mn = -1;
        cout << mn << "\n";
    }
}

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: ACCEPTED

Test 10

Group: 3, 4, 5

Verdict: ACCEPTED

Test 11

Group: 3, 4, 5

Verdict: ACCEPTED

Test 12

Group: 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 4, 5

Verdict: ACCEPTED

Test 14

Group: 4, 5

Verdict: ACCEPTED

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