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;
long long mi=1'000'000'000'000'000'000;
bool mapa[2000+9][2000+9];
bool seen[2000+9][2000+9];
long long tg[2000+9][2000+9];
long long td[2000+9][2000+9];
long long n,m,k,w1,w2,vd,vg,mk;
char c;
queue<pair<long long,long long>> q;

int main(){
    std::ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>k;
    for(int i=1;i<n+1;i++){
        for(int j=1;j<m+1;j++){
            cin>>c;
            if(c=='.')mapa[i][j]=1;
        }
    }
    q.push({1,1});
    seen[1][1]=1;
    while(!q.empty()){
        w1=q.front().first;
        w2=q.front().second;
        q.pop();
        if(!seen[w1+1][w2]&&mapa[w1+1][w2]){
            q.push({w1+1,w2});
            tg[w1+1][w2]=tg[w1][w2]+1;
            td[w1+1][w2]=td[w1][w2];
            seen[w1+1][w2]=1;
        }
        if(!seen[w1][w2+1]&&mapa[w1][w2+1]){
            q.push({w1,w2+1});
            tg[w1][w2+1]=tg[w1][w2]+1;
            td[w1][w2+1]=td[w1][w2];
            seen[w1][w2+1]=1;
        }
        if(!seen[w1][w2-1]&&mapa[w1][w2-1]){
            q.push({w1,w2-1});
            tg[w1][w2-1]=tg[w1][w2];
            td[w1][w2-1]=td[w1][w2]+1;
            seen[w1][w2-1]=1;
        }
        if(!seen[w1-1][w2]&&mapa[w1-1][w2]){
            q.push({w1-1,w2});
            tg[w1-1][w2]=tg[w1][w2];
            td[w1-1][w2]=td[w1][w2]+1;
            seen[w1-1][w2]=1;
        }
    }
//    for(int i=0;i<n+1;i++){
//        for(int j=0;j<m+1;j++){
//            cout<<"<"<<mapa[i][j]<<"> ";
//        }cout<<"\n";
//    }
//    for(int i=0;i<n+1;i++){
//        for(int j=0;j<m+1;j++){
//            cout<<"<"<<tg[i][j]<<","<<td[i][j]<<"> ";
//        }cout<<"\n";
//    }
    w1=tg[n][m];
    w2=td[n][m];
    for(int i=0;i<k;i++){
        cin>>vg>>vd;
        if(vg*w1+vd*w2<mi){
            mk=1;
            mi=vg*w1+vd*w2;
        }else if(vg*w1+vd*w2==mi){
            mk++;
        }
    }cout<<mi<<" "<<mk;
}