Hypyt

#include <bits/stdc++.h>

using namespace std;

bool contains(unordered_set<int> v, int num) {
    for (auto i : v) {
        if (i == num) {
            return true;
        }
    }
    return false;
}

int main() {
    int n, m, q, y1, x1, y2, x2;
    string row;
    cin >> n >> m >> q;
    vector<string> grid;
    vector<int> nodesInColumns[m];
    vector<vector<pair<int, pair<unordered_set<int>, unordered_set<int>>>>> row_kaaret(n);
    vector<vector<pair<int, vector<pair<unordered_set<int>,unordered_set<int>>>>>> d(n);
    for (int index = 0; index < n; index++) {
        vector<pair<int,pair<unordered_set<int>,unordered_set<int>>>> v(n, {0, {}});
        row_kaaret[index] = v;
        vector<pair<int, vector<pair<unordered_set<int>,unordered_set<int>>>>> j(n);
        d[index] = j;
    }

    for (int index = 0; index < n; index++) {
        cin >> row;
        grid.push_back(row);
        for (int col = 0; col < m; col++) {
            if (grid[index][col] == '.') {
                nodesInColumns[col].push_back(index);
            }
        }
    }
    for (int index = 0; index < m; index++) {
        for (auto node : nodesInColumns[index]) {
            for (auto node2 : nodesInColumns[index]) {
                if (node != node2) {
                    row_kaaret[node][node2].first = 1;
                    row_kaaret[node][node2].second.first.insert(index);
                    row_kaaret[node][node2].second.second.insert(index);
                }
            }
        }
    }
    //floyd
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) d[i][j].first = 0;
            else if (row_kaaret[i][j].first != 0) {
                d[i][j].first = row_kaaret[i][j].first;
                pair<unordered_set<int>,unordered_set<int>> p = row_kaaret[i][j].second;
                d[i][j].second.push_back(p);
            }
            else d[i][j].first = 1e9;
        }
    }
    /*for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << "( ";
            for (auto x : row_kaaret[i][j].second.first) {
                cout << x << " ";
            }
            cout << ")";
        }
        cout << endl;
    }*/
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (d[i][j].first > d[i][k].first + d[k][j].first) {
                    d[i][j].first = d[i][k].first + d[k][j].first;
                    row_kaaret[i][j].second.first = row_kaaret[i][k].second.first;
                    row_kaaret[i][j].second.second = row_kaaret[k][j].second.second;
                    pair<unordered_set<int>,unordered_set<int>> p;
                    p.first = row_kaaret[i][k].second.first;
                    p.second = row_kaaret[k][j].second.second;
                    d[i][j].second.clear();
                    d[i][j].second.push_back(p);//row_kaaret[i][k].second.first;
                } else if (d[i][j].first == d[i][k].first + d[k][j].first) {
                    for (auto x : row_kaaret[i][k].second.first) { 
                        row_kaaret[i][j].second.first.insert(x);
                    }
                    //row_kaaret[i][j].second.first.insert(row_kaaret[i][j].second.first.end(), row_kaaret[i][k].second.first.begin(), row_kaaret[i][k].second.first.end());
                    for (auto x : row_kaaret[k][j].second.second) { 
                        row_kaaret[i][j].second.second.insert(x);
                    }
                    //row_kaaret[i][j].second.second.insert(row_kaaret[i][j].second.second.end(), row_kaaret[k][j].second.second.begin(), row_kaaret[k][j].second.second.end());
                    pair<unordered_set<int>,unordered_set<int>> p;
                    p.first = row_kaaret[i][k].second.first;
                    p.second = row_kaaret[k][j].second.second;
                    d[i][j].second.push_back(p);
                }
            }
        }
    }
    /*for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << "( ";
            for (auto x : row_kaaret[i][j].second.first) {
                cout << x << " ";
            }
            cout << ")";
        }
        cout << endl;
    }*/
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (d[i][j].first > d[i][k].first + d[k][j].first) {
                } else if (d[i][j].first == d[i][k].first + d[k][j].first) {
                }
            }
        }
    }
    //kyselyt
    for (int index = 0; index < q; index++) {
        cin >> y1 >> x1 >> y2 >> x2;
        if (y1 == y2 && x1 == x2) cout << 0 << endl;
        else if (y1 == y2 || x1 == x2) cout << 1 << endl;
        else {
            pair<int, vector<pair<unordered_set<int>,unordered_set<int>>>> dist = d[y1-1][y2-1];
            if (dist.first >= 1e9) cout << -1 << endl;
            else {
                int a = 0, b = 0;
                for (auto pset : dist.second) {
                    if (contains(pset.second, x2-1) != false && contains(pset.first,x1-1) != false) {
                        a = 1;
                        break;
                    }
                    else if (contains(pset.second,x2-1) != false || contains(pset.first,x1-1) != false) b = 1;
                }
                if (dist.first == 1) {
                    unordered_set<int> v = row_kaaret[y1-1][y2-1].second.first;
                    unordered_set<int> v2 = row_kaaret[y1-1][y2-1].second.second;
                    if ((contains(v,x1-1) != false || contains(v2,x2-1) != false)) cout << dist.first + dist.first-1 + 1 << endl;
                    else if (contains(v,x1-1) == false && contains(v2,x2-1) == false) cout << dist.first + dist.first-1 + 2 << endl;
                } else {
                    if (a == 1) cout << dist.first + dist.first-1 << endl;
                    else if (b == 1) cout << dist.first + dist.first-1 + 1 << endl;
                    else cout << dist.first + dist.first-1 + 2 << endl;
                }
            }
        }
    }
}

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

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