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
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <limits>
#include <queue>



int main() {
    std::ios::sync_with_stdio(false);

    int n, m, k;
    std::cin >> n >> m >> k;
    std::vector<std::string> area(n);
    for(int i = 0; i < n; i++)
        std::cin >> area[i];
    std::vector<long long int> a(k), b(k);
    for(int i = 0; i < k; i++)
        std::cin >> a[i] >> b[i];
    
    std::vector<std::vector<int>> dist(n, std::vector<int>(m, -1));
    dist[0][0] = 0;
    std::queue<std::pair<int, int>> q;
    q.emplace(0, 0);
    bool found = false;
    while(!q.empty() && found == false) {
        std::pair<int, int> this_point = q.front();
        q.pop();
        int i = this_point.first, j = this_point.second;
        int this_distance = dist[i][j];
        //std::cout << "considering point " << i << " " << j << std::endl;

        std::vector<std::pair<int, int>> adjecent = { {i-1, j}, {i+1, j}, {i, j-1}, {i, j+1} };

        for(auto& point : adjecent) {
            auto [ii, jj] = point;
            if(ii >= 0 && ii < n && jj >= 0 && jj < m) {
                if(dist[ii][jj] == -1 && area[ii][jj]=='.') {
                    dist[ii][jj] = this_distance+1;
                    q.emplace(ii, jj);
                    if(ii == n-1 && jj == m-1)
                        found = true;
                }
            }
        }

    }

    int computed_distance = dist[n-1][m-1];

    long long int goes_up = n-1+m-1;
    long long int goes_down = 0;
    long long int diff = computed_distance - goes_up - goes_down;
    goes_up += diff/2;
    goes_down += diff/2;

    long long int min_effort = std::numeric_limits<long long int>::max();
    int count = 0;
    for(int i = 0; i < k; i++) {
        long long int this_effort = a[i] * goes_up + b[i] * goes_down;
        if(this_effort == min_effort)
            count++;
        else if(this_effort < min_effort) {
            min_effort = this_effort;
            count = 1;
        }
    }
    std::cout << min_effort << " " << count << std::endl;
    return 0;
}