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
#include <bits/stdc++.h>
using namespace std;
#define h 4000100
bitset<4500000> pola, odw;
vector <int> T_s[4000100];
pair <int, int> odl_p[4000100];
queue<int> q;
int y_gorny(int y_akt, int n, int m)
{
    int a=y_akt-m;
    if (a>=1) return a;
    else return h;
}
int y_dolny(int y_akt, int n, int m)
{
    int a=y_akt+m;
    if (a<=m*n) return a;
    else return h;
}
int x_prawy(int x_akt, int n, int m)
{
    int a=x_akt+1;
    if ( a<=m*n && x_akt%m!=0 ) return a;
    else return h;
}
int x_lewy(int x_akt, int n, int m)
{
    int a=x_akt-1;
    if ( a>=1 && x_akt%m!=1 ) return a;
    else return h;
}
void bfs(int v, int n, int m)
{
    q.push(v); odw[v]=true;
    while (!q.empty())
    {
        int akt_v=q.front(); q.pop();
        for (int i=0;i<T_s[akt_v].size();i++)
        {
            int v2=T_s[akt_v][i];
            if (odw[v2]) continue;
            odw[v2]=true; q.push(v2);
            if ( v2 == x_prawy(akt_v, n, m) || v2 == y_dolny(akt_v, n, m)  )
            {
                odl_p[v2].second=odl_p[akt_v].second+1; odl_p[v2].first=odl_p[akt_v].first;
            }
            else
            {
                odl_p[v2].second=odl_p[akt_v].second; odl_p[v2].first=odl_p[akt_v].first+1;
            }
        }
    }
}
int main()
{
   ios_base::sync_with_stdio(0);
   int n, m , k; cin>>n>>m>>k;
   for (int i=0;i<n;i++)
   {
       string s; cin>>s;
       for (int k=0;k<m;k++)
       {
           if ( s[k] == '.' ) pola[i*m+k+1]=true; //true to osiogalne pola
       }
   }
   int m_n = m*n;
   for (int i=1;i<=m_n;i++) //tablica somsiedztwa
   {
       if (pola[ y_gorny(i, n, m) ])  T_s[i].push_back(y_gorny(i, n, m));
       if (pola[ y_dolny(i, n, m) ])  T_s[i].push_back(y_dolny(i, n, m));
       if (pola[ x_prawy(i, n, m) ])  T_s[i].push_back(x_prawy(i, n, m));
       if (pola[ x_lewy(i, n, m) ])  T_s[i].push_back(x_lewy(i, n, m));
   }
   bfs(m_n, n, m);
   long long fastest=999999999999999999, ilu=0;
   while (k--)
   {
       long long a, b; cin>>a>>b;
       long long t_k = a*odl_p[1].first + b*odl_p[1].second;
       if ( t_k < fastest )
       {
           ilu=1; fastest=t_k;
       }
       else if ( t_k == fastest ) ilu++;
   }
   cout<<fastest<<" "<<ilu;


  return 0;
}