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
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include <bits/stdc++.h>
using namespace std;

int n,m,k;

long long typ1,typ2;

char t[2005][2005];
int odl[2005][2005];
bool odw[2005][2005];
pair<int,int> ojciec[2005][2005];

vector < pair<int,int> > G[2005][2005];
queue < pair<int,int> > Q;

map < long long, long long > M;

void BFS(int w, int k)
{
    odw[w][k] = true;

    Q.push( make_pair(w,k) );

    while(!Q.empty())
    {
        int a = Q.front().first;
        int b = Q.front().second;
        Q.pop();

        for(int i = 0; i < G[a][b].size(); i++)
        {
            int u = G[a][b][i].first;
            int v = G[a][b][i].second;

            if(!odw[ u ][ v ])
            {
                odl[u][v] = odl[a][b] + 1;
                ojciec[u][v] = make_pair(a,b);
                odw[u][v] = true;
                Q.push( make_pair(u,v) );
            }
        }
    }
}

void odtworz(int w, int k)
{
    while(w != 1 || k != 1)
    {
        if(ojciec[w][k].first + 1 == w || ojciec[w][k].second + 1 == k)
            typ1++;
        else
            typ2++;

        ///cout << w << " " << k << " " << ojciec[w][k].first << " " << ojciec[w][k].second << " " << typ1 << " " << typ2 << endl;

        pair <int, int> mem = ojciec[w][k];

        w = mem.first;
        k = mem.second;

        ///cout << w << " " << k << endl;
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m >> k;

    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            cin >> t[i][j];
        }
    }

    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            if(t[i][j] == '.')
            {
                if(t[i - 1][j] == '.')
                    G[i][j].push_back(make_pair(i - 1,j)), G[i - 1][j].push_back(make_pair(i,j));
                if(t[i + 1][j] == '.')
                    G[i][j].push_back(make_pair(i + 1,j)), G[i + 1][j].push_back(make_pair(i,j));
                if(t[i][j - 1] == '.')
                    G[i][j].push_back(make_pair(i,j - 1)), G[i][j - 1].push_back(make_pair(i,j));
                if(t[i][j + 1] == '.')
                    G[i][j].push_back(make_pair(i,j + 1)), G[i][j + 1].push_back(make_pair(i,j));
            }
        }
    }

    BFS(1,1);
    ojciec[1][1] = make_pair(-1,-1);

    odtworz(n,m);

    //cout << typ1 << " " << typ2 << endl;
/*
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            cout << "[" << ojciec[i][j].first << "][" << ojciec[i][j].second << "] ";
        }
        cout << endl;
    }

*/

long long wynik = LONG_LONG_MAX;

for(long long i = 1,a = 0, b = 0; i <= k; i++)
{
    cin >> a >> b;

    M[a * typ1  + b * typ2]++;

    if(a * typ1  + b * typ2 < wynik)
        wynik = a * typ1  + b * typ2;
}

cout << wynik << " " << M[wynik] << endl;



}