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
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;

void BFS(int n,int m,vector<string>&G,vector<vector<pair<int,int>>>&Pary)
{
    Pary[0][0]={0,0};
    queue<pair<int,int>>Q;
    Q.push({0,0});
    auto go=[&](int i,int j)
    {
        if(i==n-1 && j==m-1)
        {
            return;
        }
        if(G[i][j]=='.')
        {
            Q.push(make_pair(i,j));
        }
    };
    while(!Q.empty())
    {
        int d=Q.front().f,t=Q.front().s;
        Q.pop();
        if(d-1>=0 && Pary[d-1][t].f==-1)
        {
            Pary[d-1][t]={Pary[d][t].f,Pary[d][t].s+1};
            go(d-1,t);
        }
        if(d+1<=n-1 && Pary[d+1][t].f==-1)
        {
            Pary[d+1][t]={Pary[d][t].f+1,Pary[d][t].s};
            go(d+1,t);
        }
        if(t-1>=0 && Pary[d][t-1].f==-1)
        {
            Pary[d][t-1]={Pary[d][t].f,Pary[d][t].s+1};
            go(d,t-1);
        }
        if(t+1<=m-1 && Pary[d][t+1].f==-1)
        {
            Pary[d][t+1]={Pary[d][t].f+1,Pary[d][t].s};
            go(d,t+1);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,m,k;
    cin>>n>>m>>k;
    vector<string>V(n);
    for(int i=0;i<n;i++)
        cin>>V[i];
    vector<vector<pair<int,int>>>Pary(n,vector<pair<int,int>>(m,{-1,-1}));
    BFS(n,m,V,Pary);
    pair<long long,long long>Mnoznik=Pary[n-1][m-1],wynik={LLONG_MAX,0ll};     //wynik: 1-wartosc,2-ilosc
    while(k--)
    {
        long long a,b,pomoc=0;
        cin>>a>>b;
        pomoc=Mnoznik.f*a+Mnoznik.s*b;
        if(pomoc<wynik.f)
        {
            wynik.f=pomoc;
            wynik.s=1;
        }
        else if(pomoc==wynik.f)
        {
            wynik.s++;
        }
    }
    cout<<wynik.f<<" "<<wynik.s<<"\n";
    return 0;
}