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
#include <iostream>
#include <vector>
#include <utility>
#include <queue>
#include <set>
#include <climits>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    string str;
    set<pair<int, int>> tops;
    int n, m, k;
    cin >> n >> m >> k;
    vector<string> map(n);
    vector<vector<int>> lookmu(2000 , vector<int> (2000, INT_MAX)), lookmd(2000 , vector<int> (2000, INT_MAX)); 
    for (int i=0; n>i; i++) {
        cin >> str;
        map[i] = str;
    }
    lookmu[0][0]=0;
    lookmd[0][0]=0;
    
    vector<int> tmp = {0, 0, 0, 0};
    queue<vector<int>> q;
    q.push(tmp);
    while(!q.empty()) {
        tmp = q.front();
        q.pop();
        if (m > tmp[0] && map[tmp[1]][tmp[0]+1]=='.' && lookmu[tmp[1]][tmp[0]+1] > tmp[2]+1) {
            lookmu[tmp[1]][tmp[0]+1] = tmp[2]+1;
            q.push({tmp[0]+1, tmp[1], tmp[2]+1, tmp[3]});
        }
        if (n > tmp[1]+1 && map[tmp[1]+1][tmp[0]]=='.' && lookmu[tmp[1]+1][tmp[0]] > tmp[2]+1) {
            lookmu[tmp[1]+1][tmp[0]] = tmp[2]+1;
            q.push({tmp[0], tmp[1]+1, tmp[2]+1, tmp[3]});
        }
        if (tmp[0] > 0 && map[tmp[1]][tmp[0]-1]=='.' && lookmd[tmp[1]][tmp[0]-1] > tmp[3]+1) {
            lookmd[tmp[1]][tmp[0]-1] = tmp[3]+1;
            q.push({tmp[0]-1, tmp[1], tmp[2], tmp[3]+1});
        }
        if (tmp[1] > 0 && map[tmp[1]-1][tmp[0]]=='.' && lookmd[tmp[1]-1][tmp[0]] > tmp[3]+1) {
            lookmd[tmp[1]-1][tmp[0]] = tmp[3]+1;
            q.push({tmp[0], tmp[1]-1, tmp[2], tmp[3]+1});
        }
        if (tmp[0] == m-1 && tmp[1] == n-1) tops.insert(make_pair(tmp[2], tmp[3]));
    }
    
    int cnt = 0, a, b;
    bool f;
    long long int fastest = 9223372036854775807;
    for (int i=0; k>i; i++) {
        cin >> a >> b;
        f = 0;
        for (auto j: tops){
            if (fastest > a*j.first+b*j.second) {
                fastest = a*j.first+b*j.second;
                cnt = 1;
                f = 1;
            }
            else if (fastest == a*j.first+b*j.second && !f) {
                cnt++;
            }
        }
    }
    
    cout << fastest << " " <<  cnt << "\n";
    return 0;
}