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
#include<bits/stdc++.h>
#define ll long long
using namespace std;

bool vis[2009][2009];
bool arr[2009][2009];

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

    int n, m, k;
    cin >> n >> m >> k;
    char c;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            cin >> c;
            if(c == '.')
                arr[i][j] = true;
        }
    }
    ll res_up, res_dn;
    queue<tuple<int, int, int, int> > q;
    q.push(make_tuple(1,1,0,0));
    while(not q.empty()) {
        tuple<int, int, int, int> t = q.front();
        q.pop();
        int x = get<0>(t);
        int y = get<1>(t);
        int up = get<2>(t);
        int dn = get<3>(t);
        vis[x][y] = true;
        if(x == n and y == m) {
            res_up = up;
            res_dn = dn;
            break;
        }
        if(arr[x+1][y] and not vis[x+1][y]) {
            q.push(make_tuple(x+1, y, up+1, dn));
            vis[x+1][y] = true;
        }
        if(arr[x][y+1] and not vis[x][y+1]) {
            q.push(make_tuple(x, y+1, up+1, dn));
            vis[x][y+1] = true;
        }
        if(arr[x-1][y] and not vis[x-1][y]) {
            q.push(make_tuple(x-1, y, up, dn+1));
            vis[x-1][y] = true;
        }
        if(arr[x][y-1] and not vis[x][y-1]) {
            q.push(make_tuple(x, y-1, up, dn+1));
            vis[x][y-1] = true;
        }
    }

    ll pup, pdn;
    ll time = 1000000000000000009;
    int cnt = 0;
    for(int i = 0; i < k; i++) {
        cin >> pup >> pdn;
        if(pup * res_up + pdn * res_dn == time)
            cnt++;
        else if(pup * res_up + pdn * res_dn < time) {
            time = pup * res_up + pdn * res_dn;
            cnt = 1;
        }
    }
    cout << time << " " << cnt << "\n";

    return 0;
}