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<queue>
#include<iostream>
using namespace std;
const int limit=2007;
int odl[limit][limit];
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    long long n, m, k;
    cin>>n>>m>>k;
    char gora[n][m];
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
            cin>>gora[i][j];
    long long t[k][2];
    for(int i=0; i<k; i++){
        cin>>t[i][0]>>t[i][1];
    }
    queue<pair<int, int> > kolejka;
    kolejka.push({n-1, m-1});
    odl[n-1][m-1]=1;
    while(!kolejka.empty()){
        auto x=kolejka.front();
        kolejka.pop();
        pair<int, int> temporary[4]={{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        for(auto i:temporary){
           // cout<<x.first+i.first<<" "<<x.second+i.second<<"\n";
            if(0<=x.first+i.first && x.first+i.first<n  && 0<=x.second+i.second && x.second+i.second<m){
                if(odl[x.first+i.first][x.second+i.second]==0){
                    if(gora[x.first+i.first][x.second+i.second]=='.'){
                        kolejka.push(make_pair(x.first+i.first, x.second+i.second));
                        odl[x.first+i.first][x.second+i.second]=odl[x.first][x.second]+1;
                    }
                }
            }
        }
    }
   /* for(int i=0; i<n; i++){
        for(int j=0; j<m; j++)
            cout<<odl[i][j]<<" ";
        cout<<"\n";
    }*/
    long long wynik=odl[0][0];
    wynik-=n+m;
    wynik++;
    wynik/=2;
    long long nic=10000000000000000;
    int ile=1;
    for(int i=0; i<k; i++){
        //cout<<i<<" "<<nic<<" "<<ile<<"\n";
        long long temporary=t[i][1]*wynik;
       // cout<<temporary<<" ";
        temporary+=(n+m-2+wynik)*t[i][0];
       // cout<<temporary<<" "<<nic<<" "<<ile<<"\n";
        if(temporary==nic){
            ile++;
        //    cout<<"owkapfijo hmlnfsbjkzuacgnvb ";
        }
        if(temporary<nic){
            nic=temporary;
            ile=1;
        }
    }
    cout<<nic<<" "<<ile<<"\n";
}