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
// Marcin Knapik

// Potyczki algorytmiczne 2020 - dzien 4, zadanie C

#include<bits/stdc++.h>
using namespace std;

#define f first
#define s second
#define sz(s) (int)s.size()
#define all(s) s.begin(), s.end()

#define pb push_back
#define ii pair<int, int>
#define pii pair<ii, ii>
#define vii vector<ii>
#define ll long long

const int INF = 1e9;

int X[] = {-1, 1, 0, 0};
int Y[] = {0, 0, 1, -1};

vii sas(ii poz){
    vii ret;

    for(int i = 0; i < 4; i++){
        int x = poz.f + X[i], y = poz.s + Y[i];
        ret.pb({x, y});      
    }
    return ret;
}

int sum(ii poz){
    return poz.f + poz.s;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m, k;
    cin >> n >> m >> k;

    vector<vector<char>> tab(n + 2, vector<char> (m + 2, 'X'));

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            cin >> tab[i][j];
    
    vector<vector< ii > > dist(n + 2, vector< ii > (m + 2, make_pair(INF, INF)));
    priority_queue<pii, vector<pii>, greater<pii> > kol;

    dist[1][1] = {0, 0};
    kol.push({{0, 0}, {1, 1}});

    while(sz(kol)){
        pii akt = kol.top();
        kol.pop();

        if(akt.f != dist[akt.s.f][akt.s.s])
            continue;

        for(auto & u : sas(akt.s))
            if(tab[u.f][u.s] == '.'){
                ii koszt = (sum(u) > sum(akt.s) ? make_pair(akt.f.f, akt.f.s + 1) : make_pair(akt.f.f + 1, akt.f.s));
                if(koszt < dist[u.f][u.s]){
                    dist[u.f][u.s] = koszt;
                    kol.push({koszt, u});
                }
            }
    }

    int ile = 0;
    ll best_time = 1e18;

    for(int i = 0; i < k; i++){
        ll a, b;
        cin >> a >> b;

        ll suma = a * dist[n][m].s + b * dist[n][m].f;

        if(suma < best_time){
            ile = 0;
            best_time = suma;
        }

        if(suma == best_time)
            ile++;
    }

    cout << best_time << ' ' << ile << '\n';
}