1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <iostream>
#include <climits>

using namespace std;

//rozwiazanie zawiera algorytm Dijkstry opracowany na podstawie:
//https://mattomatti.com/pl/a0123

struct dane
{
    long long dystans;
    int poprzednik;
    bool odwiedzony;
};

int szukajMinimum(int n, dane* tab)
{
    int min = -1;
    int mindist = INT_MAX;
    for (int i = 0; i < n; i++)
    {
        if (!tab[i].odwiedzony && tab[i].dystans < mindist)
        {
            min = i;
            mindist = tab[i].dystans;
        }
    }
    return min;
}

dane* Dijkstra(int** macierz, int n, int start)
{
    dane* tab = new dane[n];
    for (int i = 0; i < n; i++)
    {
        tab[i].dystans = (i == start) ? 0 : LLONG_MAX;
        tab[i].odwiedzony = false;
        tab[i].poprzednik = -1;
    }
    int u = szukajMinimum(n, tab);
    while (u != -1)
    {
        tab[u].odwiedzony = true;
        for (int i = 0; i < n; i++)
        {
            if (macierz[u][i] > 0 && tab[u].dystans + macierz[u][i] < tab[i].dystans)
            {
                tab[i].dystans = tab[u].dystans + macierz[u][i];
                tab[i].poprzednik = u;
            }
        }
        u = szukajMinimum(n, tab);
    }
    return tab;
}

long long wypiszdane(int i, dane d) {
    return d.dystans;
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int x, y, n, s=0, m, ilosc_wedrowcow;
    int do_gory, do_dolu;

    //pobranie wspolrzednych i obliczenie ilosci wierzcholkow
    std::cin>>x; //liczba wierszy
    std::cin>>y; //liczba kolumn
    n=x*y; //liczba wierzcholkow
    //pobranie ilosci wedrowcow
    std::cin>>ilosc_wedrowcow;

    //pobranie mapy od uzytkownika jako napisu i przeksztalcenie jej w tablice znakow
    char mapa[x][y];
    string jeden_wiersz;
    for(int i=0; i<x; i++)
    {
        std::cin>>jeden_wiersz;

        for(int j=0; j<y; j++)
        {
            mapa[i][j]=jeden_wiersz[j];
        }
    }

    long long najkrotszy_czas;
    int ilosc_zwyciezcow=0;
    long long czas_wedrowca;

    for(int z=0; z<ilosc_wedrowcow; z++)
    {
        std::cin>>do_gory;
        std::cin>>do_dolu;

        //przeksztalcenie tej mapy na macierz wierzcholkow
        int** macierz = new int*[n];
        for (int i = 0; i < n; i++)
        {
            macierz[i] = new int[n];
            for (int j = 0; j < n; j++)
            {
                //jesli jestem niebezpieczenstwem lub jesli napotykam niebezpieczenstwo
                if(mapa[i/n][i%n]=='X' || mapa[j/n][j%n]=='X')
                    macierz[i][j]=0;

                //4 przypadki, kiedy moze wystapic polaczenie
                else if((j==i-1 && i%y!=0) || j==i-y) //1 i 2
                    macierz[i][j]=do_dolu;

                else if((j==i+1 && i%y!=y-1) || j==i+y) //3 i 4
                    macierz[i][j]=do_gory;

                //z pozostalymi nie ma polaczen
                else
                    macierz[i][j]=0;
            }
        }
        //znalezienie najkrotszej drogi za pomoca algorytmy Dijkstra
        dane* tab = Dijkstra(macierz, n, s);

        //wypisanie jej czas
        czas_wedrowca=wypiszdane(n-1, tab[n-1]);
        if(czas_wedrowca<najkrotszy_czas || z==0)
        {
            najkrotszy_czas=czas_wedrowca;
            ilosc_zwyciezcow=1;
        }
        else if(czas_wedrowca==najkrotszy_czas)
        {
            ilosc_zwyciezcow++;
        }
    }

    std::cout<<najkrotszy_czas<<" "<<ilosc_zwyciezcow;
    return 0;
}