Hypyt

#include <bits/stdc++.h>

using namespace std;

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<set<int>, set<int>>>>> row_kaaret(n);
    vector<vector<pair<int, set<int>>>> d(n);
    for (int index = 0; index < n; index++) {
        vector<pair<int,pair<set<int>,set<int>>>> v(n, {0, {}});
        row_kaaret[index] = v;
        vector<pair<int, 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;
                d[i][j].second = row_kaaret[i][j].second.first;
            }
            else d[i][j].first = 1e9;
        }
    }
    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;
                    d[i][j].second = row_kaaret[i][k].second.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;
                }
            }
        }
    }
    /*for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << "( ";
            for (auto x : row_kaaret[i][j].second.second) { 
                cout << x << " ";
            }
            cout << ")";
        }
        cout << endl; 
    }*/
    //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, set<int>> dist = d[y1-1][y2-1];
            if (dist.first == 1e9) cout << -1 << endl;
            else {
                int a = 0;
                if (row_kaaret[y1-1][y2-1].second.first.count(x1-1) == 0) {
                    a++;
                }
                if (row_kaaret[y1-1][y2-1].second.second.count(x2-1) == 0) {
                    a++;
                    //cout << "mui" << endl; 
                }
                if (dist.first == 1 && (row_kaaret[y1-1][y2-1].second.first.count(x1-1) != 0 || row_kaaret[y1-1][y2-1].second.second.count(x2-1) != 0)) a = 1;
                else if (dist.first == 1 && row_kaaret[y1-1][y2-1].second.first.count(x1-1) == 0 && row_kaaret[y1-1][y2-1].second.second.count(x2-1) == 0) a = 2;
                //cout << a << endl; 
                cout << dist.first + dist.first-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: 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: ACCEPTED

Test 9

Group: 3, 4, 5

Verdict: ACCEPTED

Test 10

Group: 3, 4, 5

Verdict: ACCEPTED

Test 11

Group: 3, 4, 5

Verdict: WRONG ANSWER

Test 12

Group: 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 4, 5

Verdict: ACCEPTED

Test 14

Group: 4, 5

Verdict: WRONG ANSWER

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: WRONG ANSWER

Test 19

Group: 5

Verdict: ACCEPTED

Test 20

Group: 5

Verdict: ACCEPTED

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