Hypyt

input/code.cpp: In function 'void tutkiSolmut(int, std::vector<bool>&, int, int)':
input/code.cpp:32:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for (int i = 0; i < v[currentSolmu].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~
input/code.cpp:61:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for (int i = 0; i < seuraavatSolmut1.size(); i++) // tutkitaan ensin ne solmut jotka eivät lisää pituutta lainkaan!
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~
input/code.cpp:65:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for (int i = 0; i < seuraavatSol...

#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;

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

vector<pair<int, int>> v[62500];
int grid[62500];
vector<int> distances[62500];

void tutkiSolmut(int mainSolmu, vector<bool> &visited, int currentSolmu, int aiempiSuunta)
{

    vector<pair<int, int>> seuraavatSolmut1;
    vector<pair<int, int>> seuraavatSolmut2;

    for (int i = 0; i < v[currentSolmu].size(); i++)
    {
        int u = v[currentSolmu][i].first;
        if (aiempiSuunta == -1)
        {
            if (distances[mainSolmu][u] > distances[mainSolmu][currentSolmu] + 1)
            {
                distances[mainSolmu][u] = distances[mainSolmu][currentSolmu] + 1;
                seuraavatSolmut2.push_back({u, v[currentSolmu][i].second});
            }
        }
        else if (aiempiSuunta != v[currentSolmu][i].second)
        {
            if (distances[mainSolmu][u] > distances[mainSolmu][currentSolmu] + 1)
            {
                distances[mainSolmu][u] = distances[mainSolmu][currentSolmu] + 1;
                seuraavatSolmut2.push_back({u, v[currentSolmu][i].second});
            }
        }
        else
        {
            if (distances[mainSolmu][u] > distances[mainSolmu][currentSolmu])
            {
                distances[mainSolmu][u] = distances[mainSolmu][currentSolmu];
                seuraavatSolmut1.push_back({u, v[currentSolmu][i].second});
            }
        }
    }

    for (int i = 0; i < seuraavatSolmut1.size(); i++) // tutkitaan ensin ne solmut jotka eivät lisää pituutta lainkaan!
    {
        tutkiSolmut(mainSolmu, visited, seuraavatSolmut1[i].first, seuraavatSolmut1[i].second);
    }
    for (int i = 0; i < seuraavatSolmut2.size(); i++)
    {
        tutkiSolmut(mainSolmu, visited, seuraavatSolmut2[i].first, seuraavatSolmut2[i].second);
    }
}

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 niin, että vain viereisin vapaa solmu liitetään.
    // 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[count] = 1;

                for (int i = x - 1; i >= 0; i--)
                {
                    int kohta = y * width + i;

                    if (grid[kohta] == 1)
                    {
                        v[kohta].push_back({count, 0});
                        v[count].push_back({kohta, 0});
                        break;
                    }
                    // cout << "x: " << kohta << ", " << count << " ";
                }
                for (int i = y - 1; i >= 0; i--)
                {
                    int kohta = width * i + x;

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

            count++;
        }
    }

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

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

    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[0].size(); i++)
            {
                if (v[0][i].first == count)
                {
                    isConnected = true;
                    break;
                }
            }
            if (isConnected)
            {
                cout << "1";
            }
            else
            {
                cout << "0";
            }

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

    // Suoritetaam BFS algoritmi niin, että jos liikutaan samaan suuntaan ei lisätä etäisyyttä:

    int n = height * width;

    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;
                        }
                    }
                } */

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

        vector<bool> visited(62500, 0);
        visited[c] = 1;
        distances[c][c] = 0;
        tutkiSolmut(c, visited, c, -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: WRONG ANSWER

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

Test 11

Group: 3, 4, 5

Verdict: WRONG ANSWER

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