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
#include <bits/stdc++.h>
using namespace std;
int k, mn, ile;
long long a, b, n, m;
long long najm=LLONG_MAX;
bool mapa[2010][2010];
string wej;
int odl[2010][2010];
queue<pair<int, int> > kol;

void bfs()
{
    kol.push(make_pair(0, 0));
    int w, d, x, y;
    while(!kol.empty())
    {
        w=kol.front().first;
        d=kol.front().second;
        x=w%m;
        y=w/m;
        kol.pop();
        if(d>=odl[x][y])continue;
        odl[x][y]=d;
        if(x>0&&mapa[x-1][y]&&d+1<odl[x-1][y])kol.push(make_pair(w-1, d+1));
        if(y>0&&mapa[x][y-1]&&d+1<odl[x][y-1])kol.push(make_pair(w-m, d+1));
        if(x<m-1&&mapa[x+1][y]&&d<odl[x+1][y])kol.push(make_pair(w+1, d));
        if(y<n-1&&mapa[x][y+1]&&d<odl[x][y+1])kol.push(make_pair(w+m, d));
    }
}

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    cin>>n>>m>>k;
    for(int i=0; i<n; ++i)
    {
        cin>>wej;
        for(int j=0; j<m; ++j)mapa[j][i]=(wej[j]=='.');
    }
    for(int i=0; i<n; ++i)
    {
        for(int j=0; j<m; ++j)odl[j][i]=INT_MAX;
    }
    bfs();
    mn=odl[m-1][n-1];
    for(int i=0; i<k; ++i)
    {
        cin>>a>>b;
        if(mn*(a+b)+a*(n+m-2)<najm)
        {
            ile=1;
            najm=mn*(a+b)+a*(n+m-2);
        }
        else if(mn*(a+b)+a*(n+m-2)==najm)++ile;
    }
    cout<<najm<<" "<<ile<<"\n";
}