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
88
89
#include<bits/stdc++.h>
using namespace std;
struct pole
{
    long long a=0,b=0;
    bool visited = false;
    char type = '.';
};
struct para
{
    int a,b;
};

int main()
{
    ios_base::sync_with_stdio(0);
    int n,m,z;
    cin >> n >> m >> z;
    pole tab[n][m];
    for(int k=0;k<n;k++)
        for(int i=0;i<m;i++)
            cin >> tab[k][i].type;
    queue<para> kolejka;
    kolejka.push({0,0});
    tab[0][0].visited = true;
    while(!kolejka.empty())
    {
        para t  =kolejka.front();
        //cout << "JESTEM W " << t.a << " " << t.b<<endl;
        kolejka.pop();
        if(t.a !=0)
        {
            if(!tab[t.a-1][t.b].visited && tab[t.a-1][t.b].type == '.')
            {
                tab[t.a-1][t.b].visited = true;
                kolejka.push({t.a-1,t.b});
                tab[t.a-1][t.b].b = tab[t.a][t.b].b+1;
                tab[t.a-1][t.b].a = tab[t.a][t.b].a;
            }
        }
        if(t.a != n-1)
        {
            if(!tab[t.a+1][t.b].visited && tab[t.a+1][t.b].type == '.')
            {
                tab[t.a+1][t.b].visited = true;
                kolejka.push({t.a+1,t.b});
                tab[t.a+1][t.b].a = tab[t.a][t.b].a+1;
                tab[t.a+1][t.b].b = tab[t.a][t.b].b;
            }
        }
        if(t.b !=0)
        {
            if(!tab[t.a][t.b-1].visited && tab[t.a][t.b-1].type == '.')
            {
                tab[t.a][t.b-1].visited = true;
                kolejka.push({t.a,t.b-1});
                tab[t.a][t.b-1].b = tab[t.a][t.b].b+1;
                tab[t.a][t.b-1].a = tab[t.a][t.b].a;
            }
        }
        if(t.b != m-1)
        {
            if(!tab[t.a][t.b+1].visited && tab[t.a][t.b+1].type == '.')
            {
                tab[t.a][t.b+1].visited = true;
                kolejka.push({t.a,t.b+1});
                tab[t.a][t.b+1].a = tab[t.a][t.b].a+1;
                tab[t.a][t.b+1].b = tab[t.a][t.b].b;
            }
        }
    }
    int ile = 0;
    long long lenght = 1e16;
    //cout <<"PATH"<<endl;
   // cout << tab[n-1][m-1].a << " " << tab[n-1][m-1].b <<endl;
    while(z--)
    {
        long long a,b;
        cin >> a>> b;
        if(lenght > tab[n-1][m-1].a*a + tab[n-1][m-1].b*b)
        {
            lenght = tab[n-1][m-1].a*a + tab[n-1][m-1].b*b;
            ile = 1;
        }
        else if(lenght == tab[n-1][m-1].a*a + tab[n-1][m-1].b*b)
            ile++;
    }
    cout << lenght << " " << ile <<endl;
}