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

using namespace std;
bool map[2002][2002];
// long, short, diffrent
struct {
    int sh, lg, ways;
} methods[2000][2000];

int main() {
    cin.sync_with_stdio(false);
    int n, m, k;
    cin >> n >> m >> k;
    int result= 0;
    
    struct Road {
        int sh, ln;
        inline bool operator <(const Road& other) const {
            return sh + ln < other.sh + other.ln;
        }
    };

    for (int i = 0; i < n; ++i) {
        string row;
        cin >> row;
        for (int j = 0; j < m; ++j)
            map[i][j] = (row[j] == '.' ? 1 : 0);
    }

    queue<pair<int, int>> q;
    methods[0][0] = {0, 0, 1};
    q.push(make_pair(0, 0));

    while (!q.empty()) {
        auto[x, y] = q.front();
        q.pop();
        if (x > 0 && map[x-1][y]) {
            if (methods[x-1][y].ways == 0) {
                q.push(make_pair(x-1, y));
            }
            methods[x - 1][y].ways += methods[x][y].ways;
            methods[x - 1][y].sh = methods[x][y].sh + 1;
            methods[x - 1][y].lg = methods[x][y].lg;
        }
        if (map[x+1][y]) {
            if (methods[x+1][y].ways == 0) {
                q.push(make_pair(x+1, y));
            }
            methods[x + 1][y].ways += methods[x][y].ways;
            methods[x + 1][y].sh = methods[x][y].sh;
            methods[x + 1][y].lg = methods[x][y].lg + 1;
        }
        if (y > 0 && map[x][y - 1]) {
            if (methods[x][y - 1].ways == 0) {
                q.push(make_pair(x, y - 1));
            }
            methods[x][y - 1].ways += methods[x][y].ways;
            methods[x][y - 1].sh = methods[x][y].sh + 1;
            methods[x][y - 1].lg = methods[x][y].lg;
        }
        if (map[x][y + 1]) {
            if (methods[x][y + 1].ways == 0) {
                q.push(make_pair(x, y + 1));
            }
            methods[x][y + 1].ways += methods[x][y].ways;
            methods[x][y + 1].sh = methods[x][y].sh;
            methods[x][y + 1].lg = methods[x][y].lg + 1;
        }
    }

    int best_sh = methods[n - 1][m - 1].sh;
    int best_lg = methods[n - 1][m - 1].lg;

    long long best_val = 10000000000000000;
    int best_count = 0;
    for (int i = 0; i < k; ++i) {
        long long sh, lg;
        cin >> lg >> sh;
        if (lg * best_lg + sh * best_sh == best_val) {
            ++best_count;
        }
        else if (lg * best_lg + sh * best_sh < best_val) {
            best_val = lg * best_lg + sh * best_sh;
            best_count = 1;
        }
    }
    cout << best_val << " " << best_count;
}