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
#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;

const long long inf = 1e18 + 7;
int n, m, k, a, b;
char t[2007][2007];
bool odw[2007][2007];
queue<pair<int,pair<int,int>>> q;

int bfs(int x, int y) {
    q.push({0, {x, y}});
    int odl = 0;
    while (!q.empty()) {
        x = q.front().ss.ff;
        y = q.front().ss.ss;
        odl = q.front().ff;
        //cout << x << " " << y << " " << odl << " " << n << m << "\n";
        if (x == n && y == m) {
            //cout << "***\n";
            return odl;
        }
        q.pop();
        if (!odw[x - 1][y] && t[x - 1][y] == '.') {
            odw[x - 1][y] = 1;
            q.push({odl + 1, {x - 1, y}});
        }
        if (!odw[x + 1][y] && t[x + 1][y] == '.') {
            odw[x + 1][y] = 1;
            q.push({odl + 1, {x + 1, y}});
        }
        if (!odw[x][y - 1] && t[x][y - 1] == '.') {
            odw[x][y - 1] = 1;
            q.push({odl + 1, {x, y - 1}});
        }
        if (!odw[x][y + 1] && t[x][y + 1] == '.') {
            odw[x][y + 1] = 1;
            q.push({odl + 1, {x, y + 1}});
        }
    }
    return 0;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> t[i][j];
        }
    }
    int odl = bfs(1, 1);
    int y = odl - n - m + 2;
    int x = odl - y;
    long long oa = x + y / 2, ob = y / 2, w = 0;
    int ile = 0;
    long long mi = inf;
    //cout << odl << " " << x << " " << y << " " << oa << " " << ob << "\n";
    for (int i = 0; i < k; i++) {
        cin >> a >> b;
        w = oa * (long long)a + ob * (long long)b;
        if (w < mi) {
            mi = w;
            ile = 1;
        } else if (w == mi) {
            ile++;
        }
    }
    cout << mi << " " << ile << "\n";
    return 0;
}