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
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
#include<climits>

const std::vector<std::pair<int, int>> moves = { {-1, 0}, {0, -1}, {0, 1}, {1, 0}};

int main() {

    int N,M,K;
    scanf("%d %d %d", &N, &M, &K);
    char tab[N][M+1];

    int distance[N][M+1][2];

    for (int i = 0; i < N; ++i) {
        scanf("%s", tab[i]);
    }

    for (int i = 0; i < N; ++i)
        for (int j = 0; j < M; ++j) {
            distance[i][j][0] = -1;
            distance[i][j][1] = -1;
        }

    std::queue<std::pair<int, int>> queue;
    queue.emplace(0, 0);
    distance[0][0][0] = 0;
    distance[0][0][1] = 0;

    while (!queue.empty()) {
        auto xy = queue.front(); queue.pop();
        for (const auto m : moves) {
            int x = xy.first + m.first, y = xy.second + m.second;
            if (0 <= x && x < N && 0 <= y && y < M) {
                if (distance[x][y][0] + distance[x][y][1] != -2 || tab[x][y] != '.') continue;
                distance[x][y][0] = distance[xy.first][xy.second][0];
                distance[x][y][1] = distance[xy.first][xy.second][1];
                if (x >= xy.first && y >= xy.second)
                    distance[x][y][0] += 1;
                else
                    distance[x][y][1] += 1;
                queue.emplace(x, y);
            }
        }
    }

    /*
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j)
            printf(" %d:%d", distance[i][j][0], distance[i][j][1]);
        printf("\n");
    }//*/

    long long up = distance[N-1][M-1][0];
    long long down = distance[N-1][M-1][1];

    int a, b;
    long long min_t = LLONG_MAX;
    int k = 0;
    for (int i = 0; i < K; ++i) {        
        scanf("%d %d", &a, &b);
        long long t = (up * a) + (down * b);
        //printf("%d: %lld\n", i, t);
        if (min_t > t) {
            min_t = t;
            k = 1;
        } else if (min_t == t) {
            k += 1;
        }
    }

    printf("%lld %d\n", min_t, k);

    return 0;
}