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

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define ST first
#define ND second
#define PB push_back
#define SIZE(a) ((int)a.size())

const ll INF = 1e18;

template<class T, class U>
ostream& operator<<(ostream &stream, pair<T, U> &p) {
    stream << "(" << p.ST << "," << p.ND << ")";
    return stream;
}

template<class T>
ostream& operator<<(ostream &stream, vector<T> &v) {
    stream << "[";
    for(auto elem : v) {
        stream << elem << ", ";
    }
    stream << "]";
    return stream;
}

int main() {
    ios_base::sync_with_stdio(0);
    int n, m, k;
    cin >> n >> m >> k;
    vector<string> grid(n);
    for(string &s : grid) {
        cin >> s;
    }
    int dx[] = {1, 0, -1, 0};
    int dy[] = {0, 1, 0, -1};
    vector<vector<int>> d(n, vector<int>(m, -1));
    queue<pii> q;
    d[0][0] = 0;
    q.push({0, 0});
    while(!q.empty()) {
        pii a = q.front();
        if(a.ST == n-1 && a.ND == m-1) {
            break;
        }
        q.pop();
        for(int i=0; i < 4; i++) {
            pii b = {a.ST+dx[i], a.ND+dy[i]};
            if(b.ST < 0 || b.ST >= n || b.ND < 0 || b.ND >= m || grid[b.ST][b.ND] == 'X' || d[b.ST][b.ND] != -1) {
                continue;
            }
            d[b.ST][b.ND] = d[a.ST][a.ND]+1;
            q.push(b);
        }
    }
    int z = d[n-1][m-1];
    ll y = (z-n-m+2)/2;
    ll x = n+m-2+y;
    ll minv = INF, minc = 0;
    for(int i=0; i < k; i++) {
        ll a, b;
        cin >> a >> b;
        ll val = a*x+b*y;
        if(val < minv) {
            minv = val;
            minc = 1;
        } else if(val == minv) {
            minc++;
        }
    }
    cout << minv << " " << minc << "\n";
}