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>

int n, m, k;
int a, b;
long long int wynik;
int ile;
int dl, kr;

char s[2003];
int odl[2003][2003];
bool mapa[2003][2003];
int X[]={1, 0, -1, 0};
int Y[]={0, 1, 0, -1};

bool istnieje(int x, int y)
{
    if(1<=x && x<=n && 1<=y && y<=m && mapa[x][y]==false)
        return true;
    return false;
}

void BFS()
{
    std::queue<std::pair<int, int> > q;
    q.push({1, 1});
    odl[1][1]=0;
    while(q.size()>0)
    {
        int x=q.front().first;
        int y=q.front().second;
        q.pop();
        for(int l=0; l<4; l++)
        {
            int xx=x+X[l];
            int yy=y+Y[l];
            if(istnieje(xx, yy) && odl[xx][yy]<0)
            {
                odl[xx][yy]=odl[x][y]+1;
                q.push({xx, yy});
            }
        }   
    }
}

int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for(int i=1; i<=n; i++)
    {
        scanf("%s", s);
        for(int j=1; j<=m; j++)
            if(s[j-1]=='X')
                mapa[i][j]=true;
    }
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            odl[i][j]=-1;
    BFS();
    dl=n+m-2;
    kr=(odl[n][m]-dl)/2;
    dl+=kr;
    wynik=(long long)(1000000000)*(1000000000);
    for(int i=1; i<=k; i++)
    {
        scanf("%d%d", &a, &b);
        if((long long)a*dl+(long long)b*kr<wynik)
        {
            wynik=(long long)a*dl+(long long)b*kr;
            ile=0;
        }
        if((long long)a*dl+(long long)b*kr==wynik)
            ile++;
    }
    printf("%lld %d\n", wynik, ile);
}