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

int mountain[2005][2005];
int dis[2005][2005];

queue < pair <int, int> > q;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n,m,k;
    cin >> n >> m >> k;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            char in;
            cin >> in;
            if(in=='X')mountain[i][j]=1;
        }
    }
    mountain[1][1]=-1;
    q.push(make_pair(1,1));
    while(!q.empty()){
        if(q.front().first-1>0 && mountain[q.front().first-1][q.front().second]==0){
            q.push(make_pair(q.front().first-1,q.front().second));
            dis[q.front().first-1][q.front().second]=dis[q.front().first][q.front().second]+1;
            mountain[q.front().first-1][q.front().second]=-1;
        }
        if(q.front().first+1<=n && mountain[q.front().first+1][q.front().second]==0){
            q.push(make_pair(q.front().first+1,q.front().second));
            dis[q.front().first+1][q.front().second]=dis[q.front().first][q.front().second]+1;
            mountain[q.front().first+1][q.front().second]=-1;
        }
        if(q.front().second-1>0 && mountain[q.front().first][q.front().second-1]==0){
            q.push(make_pair(q.front().first,q.front().second-1));
            dis[q.front().first][q.front().second-1]=dis[q.front().first][q.front().second]+1;
            mountain[q.front().first][q.front().second-1]=-1;
        }
        if(q.front().second+1<=m && mountain[q.front().first][q.front().second+1]==0){
            q.push(make_pair(q.front().first,q.front().second+1));
            dis[q.front().first][q.front().second+1]=dis[q.front().first][q.front().second]+1;
            mountain[q.front().first][q.front().second+1]=-1;
        }
        q.pop();
    }
    long long amount_a=n+m-2,amount_b=0;
    amount_b=(dis[n][m]-amount_a)/2;
    amount_a+=amount_b;
    long long fast_time=-1,fast_people=0;
    for(int i=0;i<k;i++){
        long long a,b;
        cin >> a >> b;
        long long result=amount_a*a+amount_b*b;
        if(fast_time==-1 || result<fast_time){
            fast_time=result;
            fast_people=1;
        }
        else if(result==fast_time)fast_people++;
    }
    cout << fast_time << " " << fast_people << "\n";

    return 0;
}