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
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>

using namespace std;

struct Field {
    bool X;
    int Cost = 100000000;
    bool Visited = false;
};

vector<vector<Field> > map;
priority_queue<tuple<int, int, int> > prio;

void addToPrio(int c, int x, int y) {
    if (map[x][y].Cost > c && !map[x][y].Visited && !map[x][y].X) {
        map[x][y].Cost = c;
        prio.push({-c, x, y});
    }
}

int main()
{
    int n, m, k;
    cin >> n >> m >> k;
    map.resize(n);
    for (int i = 0;i < n;i++) {
        map[i].resize(m);
        for (int j = 0;j < m;j++) {
            char c;
            cin >> c;
            map[i][j].X = c == 'X';
        }
    }

    map[0][0].Cost = 0;
    prio.push({0,0,0});

    while (!prio.empty())
    {
        int c, x, y;
        tie(c, x, y) = prio.top();
        prio.pop();

        c = -c;

        if (map[x][y].Visited)
            continue;

        map[x][y].Visited = true;

        if (x > 0) {
            addToPrio(c + 1, x - 1, y);
        }

        if (x < n-1) {
            addToPrio(c, x + 1, y);
        }

        if (y > 0) {
            addToPrio(c + 1, x, y - 1);
        }

        if (y < m - 1) {
            addToPrio(c, x, y + 1);
        }
    }

    int r = map[n - 1][m - 1].Cost;
    long long omin = 9223372036854775800; 
    int cmin = 0;
    for (int i = 0;i < k;i++) {
        long long a, b, tmp;
        cin >> a >> b;
        tmp = ((long long)n + (long long)m - (long long)2) * a + (long long)r * (a + b);
        if (tmp < omin) {
            omin = tmp;
            cmin = 0;
        }
        if (tmp == omin) {
            cmin++;
        }
    }

    cout << omin << " " << cmin;

}