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

int arr[2005][2005];
int dist[2005][2005];
deque<PII> Q;

void dijkstra()
{
    dist[1][1]=0;
    Q.push_front({1,1});
        while(!Q.empty())
        {
            PII u=Q.front();
            Q.pop_front();
            if(dist[u.first+1][u.second]>dist[u.first][u.second]&&arr[u.first+1][u.second]==0)
            {
                dist[u.first+1][u.second]=dist[u.first][u.second];
                Q.push_front({u.first+1,u.second});
            }
            if(dist[u.first-1][u.second]>dist[u.first][u.second]+1&&arr[u.first-1][u.second]==0)
            {
                dist[u.first-1][u.second]=dist[u.first][u.second]+1;
                Q.push_back({u.first-1,u.second});
            }
            if(dist[u.first][u.second+1]>dist[u.first][u.second]&&arr[u.first][u.second+1]==0)
            {
                dist[u.first][u.second+1]=dist[u.first][u.second];
                Q.push_front({u.first,u.second+1});
            }
            if(dist[u.first][u.second-1]>dist[u.first][u.second]+1&&arr[u.first][u.second-1]==0)
            {
                dist[u.first][u.second-1]=dist[u.first][u.second]+1;
                Q.push_back({u.first,u.second-1});
            }
        }
}

int main()
{
    ios_base::sync_with_stdio(0);
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=0;i<=n+1;i++)for(int j=0;j<=m+1;j++)arr[i][j]=1, dist[i][j]=1e9;
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)
    {
        char c;
        cin>>c;
        if(c=='.')arr[i][j]=0;
    }
    dijkstra();
    long long res=1e18;
    int cnt=0;
    while(k--)
    {
        long long a,b;
        cin>>a>>b;
        long long tmp=(n+m-2)*a+dist[n][m]*(a+b);
        if(tmp==res)cnt++;
        else if(tmp<res)res=tmp, cnt=1;
    }
    cout<<res<<" "<<cnt<<endl;
}