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
90
91
92
93
94
95
96
97
98
#include <iostream>
#include <string>
#include <vector>
#include<map>
#include <algorithm>
#include <cmath>
#include <climits>
using namespace std;
int sum = 0;
long long wynik = LLONG_MAX;
void ramka( int** tab, int m, int n)
{
    for (int i = 0; i < m + 2; i++)
        tab[i][0] = tab[i][n + 1] = -2;
    for (int i = 0; i < n + 2; i++)
        tab[0][i] = tab[m + 1][i] = -2;
}
void DFS(int** tab, int m, int n, long long sum, int g, int d)
{
    if (n == 1 && m == 1) {
        if (sum < wynik) wynik = sum;
        return;
    }
    if (tab[m][n] == -1)  tab[m][n] = sum;
    else
    {
        if (sum < tab[m][n]) tab[m][n] = sum;
    }

    if (tab[m - 1][n] == -1 || tab[m - 1][n] > sum + g)  DFS(tab, m - 1, n, sum + g, g, d);

    // ide do gory
    if (tab[m][n - 1] == -1 || tab[m][n - 1] > sum + g)  DFS(tab, m, n - 1, sum + g, g, d);  //ide do gory
    if (tab[m + 1][n] == -1 || tab[m + 1][n] > sum + d) DFS(tab, m + 1, n, sum + d, g, d); //dol
    if (tab[m][n + 1] == -1 || tab[m][n + 1] > sum + d) DFS(tab, m, n + 1, sum + d, g, d); //dol

}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    long long  m, n, t, a, b;
    char znak;
    cin >> m >> n >> t;
    int** tab = new int* [m + 3];


    for (int i = 0; i < m + 2; i++)
        tab[i] = new int[n + 3];


    ramka(tab, m, n);

    for (int x = 1; x <= m; x++)
    {
        for (int y = 1; y <= n; y++)
        {
            cin >> znak;
            if (znak == '.') tab[x][y] = -1;
            else  tab[x][y] = -2;
        }
    }

    long long  ile = 1, il = 1, l = 0;





    DFS(tab, m, n, sum, 0, 1);
    int k = m + n - 2;
    long long c = wynik;
    wynik = LLONG_MAX;
   /* while (licz > 0)
    {
        l++;
        licz -= a;
        licz -= b;
    }*/
    long long suma = 0;
    int dod = k + c;
    for (int i = 0; i < t; i++)
    {
        cin >> a >> b;
        suma = dod * a +  c* b;

        if (wynik == suma)
            ile++;
        if (wynik > suma)
        {
            wynik = suma;
            ile = 1;
        }

    }
    cout << wynik << " " << ile;
    return 0;
}