Hypyt

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

const int MAXN = 250;
const int MAXM = 250;

int n, m, q;
vector<string> grid;
vector<pair<int, int>> rows[MAXN];
vector<pair<int, int>> cols[MAXM];

int dist[MAXN][MAXM];
int visited[MAXN][MAXM];
int used_row[MAXN];
int used_col[MAXM];
int cur_gen = 1;

int bfs(int sy, int sx, int ty, int tx) 
{
    cur_gen++;

    queue<pair<int, int>> dq;
    dq.push({sy, sx});
    dist[sy][sx] = 0;
    visited[sy][sx] = cur_gen;

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

        if (y == ty && x == tx)
            return d;

        if (used_row[y] != cur_gen){
            used_row[y] = cur_gen;
            for (auto [ny, nx] : rows[y]) 
            {
                if (visited[ny][nx] != cur_gen) 
                {
                    visited[ny][nx] = cur_gen;
                    dist[ny][nx] = d + 1;
                    dq.push({ny, nx});
                }
            }
        }

        if (used_col[x] != cur_gen) {
            used_col[x] = cur_gen;
            for (auto [ny, nx] : cols[x]) 
            {
                if (visited[ny][nx] != cur_gen) 
                {
                    visited[ny][nx] = cur_gen;
                    dist[ny][nx] = d + 1;
                    dq.push({ny, nx});
                }
            }
        }
    }

    return -1;
}


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

    cin >> n >> m >> q;
    grid.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> grid[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;
        }

        int ans = bfs(y1, x1, y2, x2);
        cout << ans << "\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: 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: ACCEPTED

Test 25

Group: 5

Verdict: ACCEPTED

Test 26

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 27

Group: 5

Verdict: ACCEPTED