Hypyt

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
#include <iterator>

using namespace std;

struct edge {
    int indY;
    set<int> indX;
};

struct DistData {
    int d;
    set<int> indX;
};

int n, m, Q;

vector<vector<edge>> g;
vector<DistData> dist;
vector<vector<char>> t;

void bfs(int y0, int x0) {
    dist[y0] = {0, {x0}};
    queue<int> q;
    q.push(y0);
    while (!q.empty()) {
        int currentY = q.front();
        q.pop();
        for (auto row : g[currentY]) {
            int y = row.indY;
            auto possibleX1 = row.indX;
            auto possibleX0 = dist[currentY].indX;
            if (dist[y].d == -1) {
                set<int> interX;
                set_intersection(possibleX0.begin(), possibleX0.end(), possibleX1.begin(), possibleX1.end(), inserter(interX, interX.begin()));
                dist[y].d = dist[currentY].d + interX.empty() + 1;
                if (interX.empty()) {
                    for (int j = 0; j < m; j++) {
                        if (t[currentY][j] == '.' && t[y][j] == '.') {
                            interX.insert(j);
                        }
                    }
                }
                dist[y].indX = interX;
                q.push(y);
            }
        }
    }
}

int main() {
    cin >> n >> m >> Q;
    t.resize(n, vector<char> (m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> t[i][j];
        }
    }
    g.resize(n);
    for (int y1 = 0; y1 < n; y1++) {
        for (int y2 = 0; y2 < n; y2++) {
            set<int> xx;
            xx.clear();
            for (int j = 0; j < m; j++) {
                if (y1 == y2) continue;
                if (t[y1][j] != '.' || t[y2][j] != '.') continue;
                xx.insert(j);
            }
            if (xx.empty()) continue;
            g[y1].push_back({y2, xx});
            g[y2].push_back({y1, xx});
        }
    }
    for (int q = 0; q < Q; q++) {
        int y1, x1;
        cin >> y1 >> x1;
        y1--; x1--;
        int y2, x2;
        cin >> y2 >> x2;
        y2--; x2--;
        dist.resize(n);
        for (int i = 0; i < n; i++) {
            dist[i].d = -1;
        }
        bfs(y1, x1);
        /*for (int i = 0; i < n; i++) {
            cout << dist[i].d << ' ';
            for (int j : dist[i].indX) {
                cout << j << ' ';
            }
            cout << '\n';
        } */
        if (dist[y2].d == -1) {
            cout << -1 << '\n';
        } else {
            cout << dist[y2].d + (count(dist[y2].indX.begin(), dist[y2].indX.end(), x2) == 0) << '\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: WRONG ANSWER

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

Test 26

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 27

Group: 5

Verdict: ACCEPTED