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
#include <iostream>
#include <queue>

typedef long long ll;
using namespace std;

const int maxl=2000;
int n,m,k;
bool t[maxl+2][maxl+2];


int minl=1e9;
int was[maxl+2][maxl+2];
priority_queue<pair<int,pair<int,int>>,std::vector<pair<int,pair<int,int>>>,std::greater<pair<int,pair<int,int>>>>q;
void eval(){
    auto top=q.top();q.pop();
    int l=top.first;
    int x=top.second.first;
    int y=top.second.second;
    if(was[x][y])return;
    if(t[x][y]==0)return;
    was[x][y]=1;
    if(x==n and y==m){
        minl=min(l,minl);
        return;
    }
    q.push({l+1,{x+1,y}});
    q.push({l+1,{x-1,y}});
    q.push({l+1,{x,y+1}});
    q.push({l+1,{x,y-1}});

}


int main(){
    
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m>>k;
    char c;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>c;
            while(c!='.' and c!='X')cin>>c;
            if(c=='.')t[i][j]=1;
        }
    }
    q.push({0,{1,1}});
    while(!q.empty())eval();
    ll baza = n+m-2;
    ll ileDod= (minl - baza)/2;
    ll a,b;
    ll z[k][2];
    ll mini=1e18;
    for(int i=0;i<k;i++){
        cin>>z[i][0]>>z[i][1];
        auto l=z[i][0]*baza + (z[i][0]+z[i][1] )*ileDod;
        if(l<mini )mini=l;
    }
    int w=0;
    for(int i=0;i<k;i++){
        auto l=z[i][0]*baza + (z[i][0]+z[i][1] )*ileDod;
        if(l==mini )w++;
    }
    cout<<mini<<" "<<w<<"\n";
    
}