Hypyt

#include <iostream>
#include <vector>
#include <queue>
#include <map>
using namespace std;

int n, m, q;
vector<string> grid;
vector<vector<pair<int,int>>> rows;
vector<vector<pair<int,int>>> cols;

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

vector<int> bfs(int sy, int sx) 
{
    if (bfs_cache.count({sy,sx}) > 0)
    {
        return bfs_cache[{sy,sx}];
    }

    vector<int> dist(n * m, -1);
    vector<bool> used_rows(n, false), used_cols(m, false);
    queue<pair<int,int>> dq;

    dist[sy * m + sx] = 0;
    dq.push({sy, sx});

    while (!dq.empty()) 
    {
        auto [y, x] = dq.front();
        dq.pop();
        int d = dist[y * m + x];

        if (!used_rows[y]) {
            used_rows[y] = true;
            for (auto [ny, nx] : rows[y]) {
                int id = ny * m + nx;
                if (dist[id] == -1) {
                    dist[id] = d + 1;
                    dq.push({ny, nx});
                }
            }
        }

        if (!used_cols[x]) {
            used_cols[x] = true;
            for (auto [ny, nx] : cols[x]) {
                int id = ny * m + nx;
                if (dist[id] == -1) {
                    dist[id] = d + 1;
                    dq.push({ny, nx});
                }
            }
        }
    }

    bfs_cache[{sy,sx}] = dist;
    return dist;

}


int main() 
{
    ios::sync_with_stdio(false);

    cin >> n >> m >> q;
    grid.resize(n);
    for (int i = 0; i < n; ++i) cin >> grid[i];

    rows.assign(n, {});
    cols.assign(m, {});

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == '.') {
                rows[i].push_back({i, j});
                cols[j].push_back({i, j});
            }
        }
    }


    for (int i = 0; i < q; i++) 
    {
        int y1, x1, y2, x2;
        cin >> y1 >> x1 >> y2 >> x2;
        y1--; x1--; y2--; x2--;

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

        vector<int> ans = bfs(y1, x1);
        cout << ans[y2 * m + x2] << "\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: TIME LIMIT EXCEEDED

Test 13

Group: 4, 5

Verdict: TIME LIMIT EXCEEDED

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: RUNTIME ERROR

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

Test 25

Group: 5

Verdict: ACCEPTED

Test 26

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 27

Group: 5

Verdict: ACCEPTED