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
//Ada Kołodziejczak 
//Zadanie Wycieczka Górska

#include <bits/stdc++.h>
#define ff first
#define ss second 
#define pb push
using namespace std;
long long n, m, k, ilw;
string s[2005];
pair <long long, long long> kol[1000005];
priority_queue <pair < pair <long long, long long>, pair <long long, long long> > > pq;
long long tab[2005][2005];
pair < pair <long long, long long>, pair <long long, long long> > p;
pair <long long, long long> tw;
long long w;

int main()
{
    ios_base::sync_with_stdio(0);
    cin>>n>>m>>k;

    for(int i=0; i<n; ++i)
    {
        cin>>s[i];
    }

    for(int i=0; i<k; ++i)
    {
        cin>>kol[i].ff>>kol[i].ss;
    }

    pq.pb({{0, 0},{0,0}});
    tab[0][0]=1;

    while(!pq.empty()&&p.ss.ff<n&&p.ss.ss<m)
    {
        p=pq.top();
        pq.pop();
        if(s[p.ss.ff+1][p.ss.ss]=='.'&&tab[p.ss.ff+1][p.ss.ss]==0)
        {
            tab[p.ss.ff+1][p.ss.ss]=1;
            pq.pb({{p.ff.ff+1,p.ff.ss},{p.ss.ff+1,p.ss.ss}});
        }
        else if(s[p.ss.ff][p.ss.ss+1]=='.'&&tab[p.ss.ff][p.ss.ss+1]==0)
        {
            tab[p.ss.ff][p.ss.ss+1]=1;
            pq.pb({{p.ff.ff+1,p.ff.ss},{p.ss.ff,p.ss.ss+1}});
        }
        if(p.ss.ff>0)
        {if(s[p.ss.ff-1][p.ss.ss]=='.'&&tab[p.ss.ff-1][p.ss.ss]==0)
        {
            tab[p.ss.ff-1][p.ss.ss]=1;
            pq.pb({{p.ff.ff,p.ff.ss+1},{p.ss.ff-1,p.ss.ss}});
        }}
        if(p.ss.ss>0)
        {if(s[p.ss.ff][p.ss.ss-1]=='.'&&tab[p.ss.ff][p.ss.ss-1]==0)
        {
            tab[p.ss.ff][p.ss.ss-1]=1;
            pq.pb({{p.ff.ff,p.ff.ss+1},{p.ss.ff,p.ss.ss-1}});
        }}

        if(p.ss.ff==n-1&&p.ss.ss==m-1)
        {
            break;
        }
    }

    tw.ff=p.ff.ff;
    tw.ss=p.ff.ss;
    w=99999999999999999;

    for(int i=0; i<k; ++i)
    {
        if(kol[i].ff*tw.ff+kol[i].ss*tw.ss==w)
        {
            ++ilw;
        }
        else if(kol[i].ff*tw.ff+kol[i].ss*tw.ss<w)
        {
            ilw=1;
            w=kol[i].ff*tw.ff+kol[i].ss*tw.ss;
        }
    }

    cout<<w<<" "<<ilw;
}