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
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int N, M, K;
int Map[2002][2002];

struct Point {
    int x, y, ups, downs;
};

Point Points[5000000];
int From, To;

void tryPush(Point p) {
    if (p.x >= 0 && p.y >= 0 && p.x < M && p.y < N && Map[p.x][p.y] == 0) {
        Map[p.x][p.y] = 1;
        Points[To] = p;
        To++;
    }
}
Point pop() {
    From++;
    return Points[From - 1];
}

Point findPath() {
    tryPush({ 0, 0, 0, 0 });
    while (From < To) {
        Point p = pop();
        if (p.x == M - 1 && p.y == N - 1) {
            return p;
        }
        tryPush({ p.x + 1, p.y, p.ups + 1, p.downs });
        tryPush({ p.x, p.y + 1, p.ups + 1, p.downs });
        tryPush({ p.x - 1, p.y, p.ups, p.downs + 1 });
        tryPush({ p.x, p.y - 1, p.ups, p.downs + 1 });
    }
}

int main()
{
    scanf("%d %d %d", &N, &M, &K);
    for (int n = 0; n < N; n++) {
        for (int m = 0; m < M; m++) {
            char c;
            scanf(" %c", &c);
            Map[m][n] = c == '.' ? 0 : 1;
        }
    }
    Point p = findPath();
    int ups = p.ups;
    int downs = p.downs;
    long long int bestResult = 10000000000000000;
    int count = 0;
    for (int i = 0; i < K; i++) {
        int a, b;
        scanf(" %d %d", &a, &b);
        long long int result = (long long int)a * ups + (long long int)b * downs;
        if (result == bestResult)
            count++;
        else if (result < bestResult) {
            bestResult = result;
            count = 1;
        }
    }
    printf("%lld %d", bestResult, count);
    return 0;
}