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
#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, m, k;
    cin >> n >> m >> k;

    bool tab[n][m]; //y, x
    bool visisted[n][m];

    for(int i = 0; i < n; i++) {
        char c;
        for(int j = 0; j < m; j++) {
            scanf(" %c", &c);
            tab[i][j] = (c == '.');
        }
    }

    pair<int, int> result = make_pair(numeric_limits<int>::max() - 1, -1);

    for(int i = 0; i < k; i++) {
        int a, b;
        scanf("%d%d", &a, &b);

        memset(visisted, false, n * m);
        //memset((int64_t*)(void*)visisted, 0, (n * m) / 64);
        priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;

        pq.emplace(0, make_pair(0, 0));
        visisted[0][0] = true;

        int tr = -1;

        while(!visisted[n - 1][m - 1] && !pq.empty()) {
            auto d = pq.top();
            pq.pop();

            visisted[d.second.first][d.second.second] = true;
            tr = d.first;

            if(d.second.first > 0 && !visisted[d.second.first - 1][d.second.second] && tab[d.second.first - 1][d.second.second]) //up -> -
                pq.emplace(d.first + b, make_pair(d.second.first - 1, d.second.second));

            if(d.second.second > 0 && !visisted[d.second.first][d.second.second - 1] && tab[d.second.first][d.second.second - 1]) //left -> -
                pq.emplace(d.first + b, make_pair(d.second.first, d.second.second - 1));

            if(d.second.first < n && !visisted[d.second.first + 1][d.second.second] && tab[d.second.first + 1][d.second.second]) //down -> -
                pq.emplace(d.first + a, make_pair(d.second.first + 1, d.second.second));

            if(d.second.second < m && !visisted[d.second.first][d.second.second + 1] && tab[d.second.first][d.second.second + 1]) //right -> -
                pq.emplace(d.first + a, make_pair(d.second.first, d.second.second + 1));
        }

        if(tr == result.first) result.second++;
        else if(tr < result.first) result = make_pair(tr, 1);
    }

    cout << result.first << " " << result.second << endl;

    return 0;
}