Hypyt

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>
#include <chrono>
#include <iomanip>
#include <queue>

typedef long long ll;
using namespace std;

int grid[250][250];

struct route
{
    int x1 = -1;
    int y1 = -1;
    int x2 = -1;
    int y2 = -1;
};

vector<int> v[62500];

int main()
{

    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int height, width, operationAmount;

    cin >> height >> width >> operationAmount;

    // setupataan bellman-fordin algoritmiin tarvittava tietorakenne:
    // huomaa että painoa ei tarvita sillä etäisyys jokaiseen vierussolmuun on yksi

    int count = 0;

    for (int y = 0; y < height; y++)
    {
        for (int x = 0; x < width; x++)
        {
            char c;
            cin >> c;
            if (c == '.')
            {
                // grid[x][y] = 0;

                for (int i = 0; i < width; i++)
                {

                    int kohta = y * width + i;

                    if (kohta == count)
                        continue;

                    v[kohta].push_back(count);
                    // cout << "x: " << kohta << ", " << count << " ";
                }
                for (int i = 0; i < height; i++)
                {
                    int kohta = width * i + x;

                    if (kohta == count)
                        continue;

                    v[kohta].push_back(count);
                }
                // cout << "\n";
            }
            if (c == '*')
            {
            }

            count++;
        }
    }

/*     cout << "\n \n";


    for (int i = 0; i < v[2].size(); i++)
    {
        cout << v[2][i] << " ";
    }

    cout << "\n \n";
    count = 0;
    for (int y = 0; y < height; y++)
        {
            for (int x = 0; x < width; x++)
            {
                bool isConnected = false;
                for (int i = 0; i<v[2].size(); i++){
                    if (v[2][i] == count){
                        isConnected = true;
                        break;
                    }
                }
                if (isConnected){
                    cout << "1";
                }
                else{
                    cout << "0";
                }

                count++;
            }
            cout << "\n";
        }  */

    // Suoritetaam BFS algoritmi:

    int n = height * width;
    vector<int> distances[62500];


    for (int c = 0; c < n; c++)
    { // tehdään algoritmi joka solmulle

        vector<bool> visited(62500,0);
        vector<int> parents(62500);

        for (int i = 1; i <= n; i++)
            distances[c].push_back(1e9);

        visited[c]=1;
        distances[c][c]=0;

        queue<int> q;
        q.push(c);
        while(!q.empty()){
            int a = q.front();
            q.pop();

            for(int u: v[a]){
                if(!visited[u]){
                    visited[u] = 1;
                    q.push(u);
                    distances[c][u]=distances[c][a]+1;
                }
            }
        }


    }


/*     cout << "\n \n";
    count = 0;
    for (int y = 0; y < height; y++)
    {
        for (int x = 0; x < width; x++)
        {
            if (distances[0][count] == 1e9)
                cout << "X";
            else
                cout << distances[0][count];
            count++;
        }
        cout << "\n";
    } */

    vector<route> reitit;

    for (int i = 0; i < operationAmount; i++)
    {
        route reitti;

        int y1, x1, y2, x2;

        cin >> y1 >> x1 >> y2 >> x2;
        reitti.x1 = x1 - 1;
        reitti.y1 = y1 - 1;
        reitti.x2 = x2 - 1;
        reitti.y2 = y2 - 1;

        reitit.push_back(reitti);
    }

    for (int i = 0; i < operationAmount; i++)
    {
        int alkukohta = reitit[i].x1 + reitit[i].y1 * width;
        int loppukohta = reitit[i].x2 + reitit[i].y2 * width;
        int askelCount = distances[alkukohta][loppukohta];
        if (askelCount == 1e9)
            cout << "-1" << "\n";
        else
            cout << askelCount << "\n";
    }

    cout << "\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: 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: ACCEPTED

Test 10

Group: 3, 4, 5

Verdict: ACCEPTED

Test 11

Group: 3, 4, 5

Verdict: ACCEPTED

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

Test 25

Group: 5

Verdict: ACCEPTED

Test 26

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 27

Group: 5

Verdict: TIME LIMIT EXCEEDED