Hypyt

#include <bits/stdc++.h>

using namespace std;

bool contains(vector<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<vector<vector<int>>>> paths(n);
    vector<vector<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<int> j(n);
        d[index] = j;
        vector<vector<vector<int>>> s;
        for (int i = 0; i < n; i++) { 
            vector<vector<int>> M(m);
            s.push_back(M);
        }
        paths[index] = s;
    }

    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);
                    paths[node2][node][index].push_back(index);
                    paths[node][node2][index].push_back(index);
                }
            }
        }
    }
    //floyd
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) d[i][j] = 0;
            else if (row_kaaret[i][j].first != 0) {
                d[i][j] = row_kaaret[i][j].first;
            }
            else d[i][j] = 1e9;
        }
    }
    vector<vector<int>> clearing(m);
    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] > d[i][k] + d[k][j]) {
                    d[i][j] = d[i][k] + d[k][j];
                    row_kaaret[i][j].second.first = row_kaaret[i][k].second.first;
                    row_kaaret[i][j].second.second = row_kaaret[k][j].second.second;
                    paths[i][j] = clearing;
                    paths[j][i] = clearing;
                    for (auto x : row_kaaret[i][k].second.first) { 
                        paths[i][j][x].insert(paths[i][j][x].end(), row_kaaret[k][j].second.second.begin(), row_kaaret[k][j].second.second.end());
                    }
                    for (auto x : row_kaaret[k][j].second.second) { 
                        cout << row_kaaret[i][k].second.first.size() << endl; 
                        cout << i << " " << j << " " << x  << endl; 
                        paths[j][i][x].insert(paths[i][j][x].end(), row_kaaret[i][k].second.first.begin(), row_kaaret[i][k].second.first.end());
                    }
                } else if (d[i][j] == d[i][k] + d[k][j]) {
                    row_kaaret[i][j].second.first.insert(row_kaaret[i][k].second.first.begin(), row_kaaret[i][k].second.first.end());
                    row_kaaret[i][j].second.second.insert(row_kaaret[k][j].second.second.begin(), row_kaaret[k][j].second.second.end());
                    for (auto x : row_kaaret[i][k].second.first) { 
                        paths[i][j][x].insert(paths[i][j][x].begin(),row_kaaret[k][j].second.second.begin(),row_kaaret[k][j].second.second.end());
                    }
                    for (auto x : row_kaaret[k][j].second.second) { 
                        paths[j][i][x].insert(paths[j][i][x].begin(),row_kaaret[i][k].second.first.begin(),row_kaaret[i][k].second.first.end());
                    }
                }
            }
        }
    }
    //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 {
            int dist = d[y1-1][y2-1];
            if (dist >= 1e9) cout << -1 << endl;
            else {
                int a = 2;
                if (!paths[y1-1][y2-1][x1-1].empty()) {
                    if (contains(paths[y1-1][y2-1][x1-1], x2-1)) {
                        a--;
                    }
                    a--;
                }
                else if (!paths[y2-1][y1-1][x2-1].empty()) {
                    a--;
                }
                cout << dist + dist-1 + a << 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: RUNTIME ERROR

Test 4

Group: 1, 2, 3, 4, 5

Verdict: RUNTIME ERROR

Test 5

Group: 1, 2, 3, 4, 5

Verdict: RUNTIME ERROR

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

Test 12

Group: 4, 5

Verdict: ACCEPTED

Test 13

Group: 4, 5

Verdict: ACCEPTED

Test 14

Group: 4, 5

Verdict: RUNTIME ERROR

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

Test 20

Group: 5

Verdict: RUNTIME ERROR

Test 21

Group: 5

Verdict: RUNTIME ERROR

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: TIME LIMIT EXCEEDED