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
#include <bits/stdc++.h>
using namespace std;
int t_w, t_h;
char tab[2000][2000];
long long up_count = 0;
long long down_count = 0;
void bfs() {
    queue<int>Q;
    int w, k, i, j;
    Q.push(0);
    Q.push(0);
    while (!Q.empty()) {
        w = Q.front();
        Q.pop();
        k = Q.front();
        Q.pop();
        if ((w+1 == t_w) && (k+1 == t_h))
            break;
        for (i = -1; i <= 1; i++)
            for (j = -1; j <= 1; j++)
                if ((i != j) && (!i || !j))
                {
                    if (w + i < 0 || k + j < 0 || w + i >= t_w || k + j >= t_h)
                        continue;
                    if (tab[w + i][k + j] == '.')
                    {
                        if (i == -1) tab[w + i][k + j] = 'd';
                        else if (i == 1) tab[w + i][k + j] = 'g';
                        else if (j == -1) tab[w + i][k + j] = 'p';
                        else               tab[w + i][k + j] = 'l';
                        Q.push(w + i);
                        Q.push(k + j);
                    }
                }
    }
    return;
}
void check_length() {
    int x = t_w-1;
    int y = t_h-1;
    while (x||y) {
        if (tab[x][y] == 'd') {
            down_count++;
            x++;
        }
        if (tab[x][y] == 'p') {
            down_count++;
            y++;
        }
        if (tab[x][y] == 'l') {
            up_count++;
            y--;
        }
        if (tab[x][y] == 'g') {
            up_count++;
            x--;
        }
    }
}
int main() {
    char s;
    int persons;
    scanf("%d %d %d",&t_w,&t_h,&persons);
    for (int i = 0; i < t_w; i++) {
        for (int j = 0; j < t_h; j++)
        {
            s=getchar();
            if(s!='.'&&s!='X'){
                j--;
                continue;
            }
            tab[i][j] = s;
        }
    }
    bfs();
    check_length();
    long long up_speed, down_speed;
    map<long long, long long> results;
    long long min = -1;
    long long current;
    for (int i = 0; i < persons; i++)
    {
        scanf("%lld %lld",&up_speed,&down_speed);
        current = up_speed * up_count + down_speed * down_count;
        results[current]++;
        if (min == -1 || current < min)
            min = current;
    }
    printf("%lld %lld",min,results[min]);
}