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

bool foo(int i, int j, int n, int m) {
    return 0 <= i && i < n && 0 <= j && j < m;
}

void test_case() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<string> grid(n);
    for (int i = 0; i < n; i++)
        cin >> grid[i];
    vector<vector<bool>> seen(n, vector<bool>(m));
    vector<vector<int>> dist(n, vector<int>(m, 1e9+1));
    queue<pair<int, int>> q;
    seen[0][0] = true;
    dist[0][0] = 0;
    q.push({0, 0});
    while (!q.empty()) {
        auto p = q.front();
        q.pop();
        int i = p.first, j = p.second;
        if (foo(i+1, j, n, m) && !seen[i+1][j] && grid[i+1][j] != 'X') {
            seen[i+1][j] = true;
            dist[i+1][j] = dist[i][j] + 1;
            q.push({i+1, j});
        }
        if (foo(i, j+1, n, m) && !seen[i][j+1] && grid[i][j+1] != 'X') {
            seen[i][j+1] = true;
            dist[i][j+1] = dist[i][j] + 1;
            q.push({i, j+1});
        }
        if (foo(i-1, j, n, m) && !seen[i-1][j] && grid[i-1][j] != 'X') {
            seen[i-1][j] = true;
            dist[i-1][j] = dist[i][j] + 1;
            q.push({i-1, j});
        }
        if (foo(i, j-1, n, m) && !seen[i][j-1] && grid[i][j-1] != 'X') {
            seen[i][j-1] = true;
            dist[i][j-1] = dist[i][j] + 1;
            q.push({i, j-1});
        }
    }
    int64_t sum = dist[n-1][m-1];        // x - y = m + n - 2
    int64_t y = (sum - (m + n - 2)) / 2; // x = m + n - 2 + y
    int64_t x = sum - y;                 // x + y = m + n - 2 + 2 * y
    int64_t ans = 1e18+1;                // sum   = m + n - 2 + 2 * y
    vector<int64_t> a(k), b(k);
    for (int i = 0; i < k; i++) {
        cin >> a[i] >> b[i];
        ans = min(ans, a[i]*x + b[i]*y);
    }
    int cnt = 0;
    for (int i = 0; i < k; i++) {
        cnt += (a[i]*x + b[i]*y == ans);
    }
    cout << ans << ' ' << cnt << '\n';
}

void solve() {
    test_case();
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    solve();

    return 0;
}