Hypyt

input/code.cpp: In function 'void tutkiSolmut(int, std::vector<bool>&)':
input/code.cpp:51:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |             for (int i = 0; i < v[currentParentSolmu.first].size(); i++)
      |                             ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

#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)
{

    vector<pair<int, int>> nextDistSolmut;

    queue<pair<int, int>> qMain;
    qMain.push({mainSolmu, -1}); // tänne seuraavan distancen solmut

    while (!qMain.empty())
    {

        pair<int, int> distanceSolmu = qMain.front();
        qMain.pop();

        /* if (mainSolmu == 8)
            cout << "DISTANCE:  " << distances[mainSolmu][distanceSolmu.first] << " \n"; */

        queue<pair<int, int>> q;
        q.push(distanceSolmu);

        while (!q.empty()) // ensin selvitetään kaikki tämän distancen solmut ja myöhemmin seuraavan distancen.
        {
            pair<int, int> currentParentSolmu = q.front();
            q.pop();

            for (int i = 0; i < v[currentParentSolmu.first].size(); i++)
            {
                pair<int, int> currentSolmu = v[currentParentSolmu.first][i];

                if (!visited[currentSolmu.first])
                {

                    visited[currentSolmu.first] = 1;

                    if (currentParentSolmu.second == -1 || currentParentSolmu.second != v[currentParentSolmu.first][i].second)
                    {
                        distances[mainSolmu][currentSolmu.first] = distances[mainSolmu][currentParentSolmu.first] + 1;
                        qMain.push(currentSolmu);
                        /* if (mainSolmu == 8)
                            cout << "PUSH: " << currentParentSolmu.first << " " << currentSolmu.first << " \n"; */
                    }
                    else
                    {
                        distances[mainSolmu][currentSolmu.first] = distances[mainSolmu][currentParentSolmu.first];
                        q.push(currentSolmu);
                        /* if (mainSolmu == 8)
                            cout << "SET: " << currentParentSolmu.first << " " << currentSolmu.first << " \n"; */
                    }
                }
                else if(!(currentParentSolmu.second == -1 || currentParentSolmu.second != v[currentParentSolmu.first][i].second) && distances[mainSolmu][currentParentSolmu.first] < distances[mainSolmu][currentSolmu.first]){
                    distances[mainSolmu][currentSolmu.first] = distances[mainSolmu][currentParentSolmu.first];
                    q.push(currentSolmu);
                    /* if (mainSolmu == 8)
                    cout << "OVERRIDE SET: " << currentParentSolmu.first << " " << currentSolmu.first << " \n"; */
                }
            }
           /*  if (mainSolmu == 8)
                cout << "CHILDS DONE: " << currentParentSolmu.first << " \n"; */
        }
    }
}

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[8].size(); i++)
    {
        cout << v[8][i].first << " " << v[8][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[8].size(); i++)
            {
                if (v[8][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);
    }

    /* cout << "\n \n";
    count = 0;
    for (int y = 0; y < height; y++)
    {
        for (int x = 0; x < width; x++)
        {
            if (distances[8][count] == 1e9)
                cout << "X";
            else
                cout << distances[8][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: WRONG ANSWER

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

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