Hypyt

#include <iostream>
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;


int n, m, q;
int main() {
    //ios_base::sync_with_stdio(0);
    //cin.tie(0);
    //cout.tie(0);
    cin >> n>>m>>q;
    vector<vector<char>> r(n+1, vector<char>(m+1));
    vector<vector<pair<int, int>>>v(n+1); //v[rivi_id].push_back({rivi_id, x}) //vieruslista
    vector<vector<int>> e(n+1, vector<int>(n+1,1e9)); //etäisyydet e[i][j] etäisyys i:riviltä j:riville
    //vector<vector<pair<vector<int>, vector<int>>>> p(n+1, vector<pair<vector<int>,vector<int>>>(n+1)); //p[alku][loppu].first = [aloikusen x:t] 
    vector<vector<pair<vector<pair<int,int>>, vector<pair<int,int>>>>> p(n+1, vector<pair<vector<pair<int,int>>,vector<pair<int,int>>>>(n+1)); //pair<x-akseli, y-akseli>
    //vector<vector<pair<vector<int>, vector<int>>>> p(n+1, vector<pair<vector<int>,vector<int>>>(n+1)); //pair<x-akseli, y-akseli>
  

    for (int i =1; i<=n;i++) {
        string s;
        cin>>s;
        for (int j = 1; j<=m;j++) {
            r[i][j] = s[j-1];
            if (r[i][j] == '.') {

            }
        }
    }
    //vierusmatriisi
    for (int i = 1; i<=n;i++) {
        e[i][i] = 0;
        for (int j = 1;j<=m;j++) {
            if (r[i][j] == '.') {
                for (int k = 1; k<=n;k++) { //y-akseli
                    if (r[k][j] == '.' && k != i) {
                        v[i].push_back({j, k});
                        e[i][k] = 2; //voi vähentää lopussa 1 jos samassa sarakkeessa
                        p[i][k].first.push_back({j, k});
                        p[i][k].second.push_back({j, i}); //vai tähänkin k??
                    }    
                }
            }
        }
    }
    
    //for (int i = 1;i<=n;i++) {
    //    cout <<i<<":\n";
    //for (auto p : v[1]) {
    //    cout <<p.first<<" " <<p.second<<"\n";
    //}
 
    
    //FLOYD-WARSHALL
    for (int k = 1;k<=n;k++) { //välisolmu
        for (int i = 1;i<=n;i++) { //alkusolmu
            for (int j = 1;j<=n;j++) { //loppusolmu

                if (e[i][j] > e[i][k] + e[k][j]) {

                    e[i][j] = e[i][k] + e[k][j];
                    for (auto d : p[i][k].first) {
                        p[i][j].first.push_back(d);
                    }
                    for (auto d : p[k][j].second) {
                        p[i][j].second.push_back(d);
                    }
                }
     
            }
        }
    }
    //cout <<"1 aloitus\n";
    //for (auto a : p[1][3].first) {
    //    cout <<"reitti 1 => 3 voi alkaa x:lla "<<a<<"\n";   
    //}
    //for (auto a : p[1][3].second) {
    //    cout <<"reitti 1 => 3 voi loppua x:lla "<<a<<"\n";   
    //}

    for (int i = 0;i<q;i++) {
        int y1, x1, y2,x2;
        cin >>y1>>x1>>y2>>x2;
        //tarkista jos samaa saraketta
        //cout<<"---\n";
        if (y1 == y2 && x1 == x2) {
            cout <<"0\n";
        } else if (e[y1][y2] >= 1e9 || r[y1][x1] == '*' || r[y2][x2] == '*') {
            cout <<"-1\n";
        } else if (y1 == y2 || x1 == x2) {
            cout <<"1\n";
        } 
        else {
            int ans = e[y1][y2];
            //cout <<ans<<"\n";
            bool alku = false;
            bool loppu = false;

            bool f = false;
            for (auto j : p[y1][y2].first) {
                //cout <<j<<" x-koordinaatti joka aloittaa alku-loppu\n";
                if (j.first == x1) { 
                    alku = true;
                    if (j.second == y2) { //poistaa kaksoisreitit??
                        cout <<ans<<"\n";
                        f = true;
                        break;
                    }
                    //cout <<"ei alkulisaa\n";
                }
            } 
            if (f) {
                continue;
            }
            for (auto j : p[y1][y2].second) {
                //cout <<j<<" x-koordinaatti joka lopettaa alku-loppu\n";
                if (j.first == x2) {
                    loppu = true;
                    if (j.second == y1) {
                        cout <<ans <<"\n"; //ei pitäisi tapahtua tätä koskaan, koska alkua tarkastellessa olisi huomattu
                        f = true;
                        break;
                    }
                }
            } 
            if (f) {
                continue;
            }
            if (alku == false) {
                ans += 1;
                //cout <<"lisataan, koska alku ei suoraan\n";
            }             
            if (loppu == true) {
                //cout <<ans<<"\n";
                ans = ans-1;
                //cout <<"vahennetaan, koska loppu suoraan oikein\n";
            }  
            cout <<ans <<"\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: ACCEPTED

Test 7

Group: 2, 5

Verdict: ACCEPTED

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

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

Test 17

Group: 5

Verdict: ACCEPTED

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