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
#include <bits/stdc++.h>
#include <limits>
using namespace std;

#define int long long

main()
{
    int n,m,k;
    cin>>n>>m>>k;
    vector<string> T(n+2);
    for(int i=0; i<m+2; i++)
        T[0]+='X';
    for(int i=1; i<=n; i++)
    {
        T[i]='X';
        string s;
        cin>> s;
        T[i]+=s;
        T[i]+='X';
    }
    for(int i=0; i<m+2; i++)
        T[n+1]+='X';
    queue<tuple<int,int,int,int> >q;
    q.push(make_tuple(1,1,0,0));
    vector<pair<int,int> > w;
    vector<vector<pair<int,int> > > D(n+2, vector<pair<int,int> >(m+2, make_pair(9223372036854775807,9223372036854775807)));
    while(!q.empty())
    {
        tuple<int,int,int,int> t=q.front();
        q.pop();
        if(T[get<0>(t)-1][get<1>(t)]=='.' && D[get<0>(t)-1][get<1>(t)].second>get<3>(t))
        {
            q.push(make_tuple(get<0>(t)-1, get<1>(t), get<2>(t)+1, get<3>(t)));
            D[get<0>(t)-1][get<1>(t)].second=get<3>(t);
            D[get<0>(t)-1][get<1>(t)].first=get<2>(t)+1;

        }
        if(T[get<0>(t)][get<1>(t)-1]=='.' && D[get<0>(t)][get<1>(t)-1].second>get<3>(t) )
        {
            q.push(make_tuple(get<0>(t), get<1>(t)-1, get<2>(t)+1, get<3>(t)));
            D[get<0>(t)][get<1>(t)-1].second=get<3>(t);
            D[get<0>(t)][get<1>(t)-1].first=get<2>(t)+1;
        }
        if(T[get<0>(t)+1][get<1>(t)]=='.' && D[get<0>(t)+1][get<1>(t)].second>get<3>(t)+1)
        {
            q.push(make_tuple(get<0>(t)+1, get<1>(t), get<2>(t), get<3>(t)+1));
            D[get<0>(t)+1][get<1>(t)].second=get<3>(t)+1;
            D[get<0>(t)+1][get<1>(t)].first=get<2>(t);
        }
        if(T[get<0>(t)][get<1>(t)+1]=='.' && D[get<0>(t)][get<1>(t)+1].second>get<3>(t)+1)
        {
            q.push(make_tuple(get<0>(t), get<1>(t)+1, get<2>(t), get<3>(t)+1));
            D[get<0>(t)][get<1>(t)+1].second=get<3>(t)+1;
            D[get<0>(t)][get<1>(t)+1].first=get<2>(t);
        }
    }
    int ile=0;
    int m1=9223372036854775807;
    for(int i=0; i<k; i++)
    {
        int a,b;
        cin>>a>>b;
        int m2=(D[n][m].first*b)+(D[n][m].second*a);
        if(m2<m1)
        {
            ile=1;
            m1=m2;
        }
        else if(m2==m1)
        {
            ile++;
        }
    }
    cout<<m1<<" "<<ile;
}