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

using namespace std;

const long long int inf = 1e18+7;

inline bool inbounds(const int& x,const int& y,const int& n,const int& m){return x>=0&&x<n&&y>=0&&y<m;}

long long int bfs(vector<vector<bool>>& t,vector<vector<long long>>& d){
    pair<int,int> p;
    int x,y;
    queue<pair<int,int>>q;
    q.push(make_pair(0,0));
    d[0][0]=0;
    int pom[]={0,1,0,-1,0};
    while(!q.empty()){
        p=q.front();
        q.pop();
        if(p.first==int(t.size())-1&&p.second==int(t.back().size())-1)return d.back().back();
        for(int i=0;i<4;i++){
            x=p.first+pom[i];
            y=p.second+pom[i+1];
            if((inbounds(x,y,t.size(),t.back().size())&&t[x][y])&&d[p.first][p.second]+1<d[x][y]){
                d[x][y]=d[p.first][p.second]+1;
                q.push(make_pair(x,y));
            }
        }
    }
    return d.back().back();
}

int main(){
    long long n,m,p,M=inf,a,b;
    int k,wyn=0;
    char c;
    cin >> n >> m >> k;
    vector<vector<bool>>t(m,vector<bool>(n,true));
    vector<vector<long long>>d(m,vector<long long>(n,inf));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin >> c;
            t[j][i]=(c=='.');
        }
    }
    p=(bfs(t,d)-(--n)-(--m))/2;
    for(int i=0;i<k;i++){
        cin >> a >> b;
        if((n+m)*a+p*(a+b)<M){
            wyn=1;
            M=(n+m)*a+p*(a+b);
        }
        else if((n+m)*a+p*(a+b)==M)wyn++;
    }
    cout << M << " " << wyn << endl;
}