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
#include <bits/stdc++.h>
#include <iostream>

using namespace std;
queue< pair <int, int>> kolej;
int score[2002][2002];
bool odw[2002][2002];
int n, m, k;
bool mapa[2002][2002];
pair <int, int> dirs[4] = {{-1, 0}, {1, 0}, {0, -1}, {0,1}};
void bfsuj() {
    while (!kolej.empty()) {
        pair <int, int> curr = kolej.front();
        int x = curr.first;
        int y = curr.second;
        kolej.pop();
        for (pair <int, int> dir : dirs) {
            int x_ = x + dir.first;
            int y_ = y + dir.second;
            if ((!odw[x_][y_]) && mapa[x_][y_]) {
                odw[x_][y_] = 1;
                score[x_][y_] = score[x][y] + 1;
                kolej.push({x_, y_});
            }
        }
    }
}

int main() {
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            char place;
            cin >> place;
            if (place == '.') {
                mapa[i][j] = 1;
            }
        }
    }

    kolej.push({1, 1});
    odw[1][1] = 1;
    bfsuj();
    long long c = (score[n][m] - (n + m - 2))/2;

    long long best = 1000000000000000000LL;
    long long how_many = 0;
    while (k--) {
        long long a, b;
        cin >> a >> b;
        long long my_score = a*(n+m-2) + c*(a+b);
        if (my_score == best) {
            how_many++;
        } else if (my_score < best) {
            best = my_score;
            how_many = 1;
        }
    }
    cout << best << " " << how_many << endl;
    return 0;
}