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
#include <iostream>
#include <vector>
using namespace std;

const int ruchy[4][2] = { {1,0},{0,1},{-1,0},{0,-1} };

void ruch(char** plansza, unsigned long long int w, unsigned long long int k, unsigned long long int r_gora, unsigned long long int r_dol, unsigned long long int roz_w, unsigned long long int roz_k, vector <pair<int, int>> *wek);
bool czy_mozna(char** plansza, unsigned long long int w, unsigned long long int k, unsigned long long int roz_w,  unsigned long long int roz_k);

int main()
{
    vector <pair<int, int>> rezultat;
    unsigned long long int n, m, k;
    cin >> n >> m >> k;
    char** plansza;
    plansza = new char* [n];
    for (unsigned long long int i = 0; i < n; i++) {
        plansza[i] = new char[m];
    }
    for (unsigned long long int i = 0; i < n; i++) {
        for (unsigned long long int x = 0; x < m; x++) {
            cin >> plansza[i][x];
        }
    }
    vector <pair<int, int>>szybkosc;
    for (int i = 0; i < k; i++) {
        unsigned long long int gora, dol;
        cin >> gora >> dol;
        pair<unsigned long long int, unsigned long long int> speed(gora, dol);
        szybkosc.push_back(speed);

    }
    ruch(plansza, 0, 0, 0, 0, n, m, &rezultat);
    int flaga = 0;
    unsigned long long int licznik = 0;
    unsigned long long int min = szybkosc[0].first * rezultat[0].first + szybkosc[0].second * rezultat[0].second;
    for (int i = 0; i < k; i++)
    {
        flaga = 0;
        for (unsigned long long int x = 0; x < rezultat.size(); x++) {
            if (szybkosc[i].first * rezultat[x].first + szybkosc[i].second * rezultat[x].second == min&&flaga==0) {
                licznik++;
                flaga = 1;
            }
            else if (szybkosc[i].first * rezultat[x].first + szybkosc[i].second * rezultat[x].second < min)
            {
                licznik = 1;
                min = szybkosc[i].first * rezultat[x].first + szybkosc[i].second * rezultat[x].second;
            }
        }
    }
    /*for (int i = 0; i < rezultat.size(); i++) {
        cout <<"miju miju "<< rezultat[i].first << " " << rezultat[i].second << "\n";
    }*/
    cout << min << " " << licznik;
}

void ruch(char** plansza, unsigned long long int w, unsigned long long int k, unsigned long long int r_gora, unsigned long long int r_dol, unsigned long long int roz_w, unsigned long long int roz_k, vector <pair<int, int>>* wek) {
    plansza[w][k] = '1';
    //cout << w << " " << k << "\n";
    if (w == roz_w - 1 && k == roz_k - 1) {
        pair<unsigned long long int, unsigned long long int> wynik (r_gora,r_dol);
        //cout << "Wynik: "<<r_gora+r_dol<<"\n";
        (*wek).push_back(wynik);
    }
    for (int i = 0; i < 4; i++) {
        if (czy_mozna(plansza, w + ruchy[i][0], k + ruchy[i][1], roz_w, roz_k)) {
                if (ruchy[i][0]==1||ruchy[i][1]==1)
                {
                    ruch(plansza, w + ruchy[i][0], k + ruchy[i][1], r_gora + 1, r_dol, roz_w, roz_k, wek);
                    
                }
                else {
                    ruch(plansza, w + ruchy[i][0], k + ruchy[i][1], r_gora, r_dol + 1, roz_w, roz_k, wek);
                }
        }
    }
    plansza[w][k] = '.';
}

bool czy_mozna(char** plansza, unsigned long long int w, unsigned long long int k, unsigned long long int roz_w, unsigned long long int roz_k) {
    return w>=0&&w<roz_w&&k>=0&&k<roz_k&&plansza[w][k]!='X'&& plansza[w][k] != '1';
}