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

using namespace std;
int n, m, k;
const int N = 2009;
long long INF = 1e16;
char board[N][N];
bool vis[N][N];
vector< pair<int, int> > wnd;

pair<int, int> bfs()
{
    queue< tuple<int, int, int, int> > qu; // 0 w,  1 k,  2 dol,  3 gora
    qu.push(make_tuple(1, 1, 0, 0));
    while(!qu.empty()) {
        auto curr_vert = qu.front();
        qu.pop();
        int i = get<0>(curr_vert), j = get<1>(curr_vert);
        if(i == n && j == m) {
            return make_pair(get<2>(curr_vert), get<3>(curr_vert));
        }
        vis[i][j] = true;
        if(board[i - 1][j] == '.' && !vis[i - 1][j]) {
            qu.push(make_tuple(i - 1, j, get<2>(curr_vert), get<3>(curr_vert) + 1));
        }
        if(board[i + 1][j] == '.' && !vis[i + 1][j]) {
            qu.push(make_tuple(i + 1, j, get<2>(curr_vert) + 1, get<3>(curr_vert)));
        }
        if(board[i][j - 1] == '.' && !vis[i][j - 1]) {
            qu.push(make_tuple(i, j - 1, get<2>(curr_vert), get<3>(curr_vert) + 1));
        }
        if(board[i][j + 1] == '.' && !vis[i][j + 1]) {
            qu.push(make_tuple(i, j + 1, get<2>(curr_vert) + 1, get<3>(curr_vert)));
        }
    }
}

pair<long long, int> solv()
{
    pair<long long, int> sol = {INF, 0};
    auto shrt_path = bfs();
    for(auto i : wnd) {
        long long curr_time = (long long)shrt_path.first * i.first + (long long)shrt_path.second * i.second;
        if(curr_time < sol.first) {
            sol = {curr_time, 1};
        }
        else if(curr_time == sol.first) {
            sol.second++;
        }
    }
    return sol;
}

int main()
{   
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i++) {
        string word;
        cin >> word;
        for(int j = 0; j < word.size(); j++)
            board[i][j + 1] = word[j];
    }
    for(int i = 0; i < k; i++) {
        int a, b;
        cin >> a >> b;
        wnd.push_back(make_pair(a, b));
    }
    auto sol = solv();
    cout << sol.first << ' ' << sol.second;


    return 0;
}