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
 99
100
101
102
103
104
105
106
#include <bits/stdc++.h>

using namespace std;

#define N 2000

int odw[N][N];
int odl[N][N];
vector<pair<int,int>> graf[N][N];
pair<int,int> rodzic[N][N];

void BFS(pair<int, int> p)
{
    odw[p.first][p.second]=1;
    queue<pair<int, int>> bfs;
    bfs.push(p);
    while (!bfs.empty())
    {
        pair<int,int> x=bfs.front();
        bfs.pop();
        for (auto y: graf[x.first][x.second])
        {
            if(!odw[y.first][y.second])
            {
                odl[y.first][y.second]=odl[x.first][x.second]+1;;
                odw[y.first][y.second]=1;
                rodzic[y.first][y.second] = x;
                bfs.push(y);
            }
        }
    }
}

main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, m, c;
    cin >> n >> m >> c;

    char z;
    bool tab[n][m];

    for (int y = 0; y < n; ++y)
    {
        for (int x = 0; x < m; ++x)
        {
            cin >> z;
            if (z == '.')
            {
                tab[x][y] = true;

                if (y > 0)
                {
                    if (tab[x][y-1])
                    {
                        graf[x][y].push_back(pair<int, int>(x,y-1));
                        graf[x][y-1].push_back(pair<int, int>(x, y));
                    }
                }
                if (x > 0)
                {
                    if (tab[x-1][y])
                    {
                        graf[x][y].push_back(pair<int, int>(x-1,y));
                        graf[x-1][y].push_back(pair<int, int>(x,y));
                    }
                }
            }
            else
                tab[x][y] = false;
        }
    }
    BFS({0,0});
    pair<int,int> a = {m-1, n-1};
    pair<int,int> b;

    pair<long long, long long> droga = {0,0};

    cout << m+n-2 << ' ' << odl[m-1][n-1] << '\n';

    droga.first = m+n-2+(odl[m-1][n-1]-m-n+2)/2;
    droga.second = (odl[m-1][n-1]-m-n+2)/2;

    long long minimum = LLONG_MAX;
    int liczba = 0;
    long long g, d;
    long long czas;


    for (int i = 0; i < c; ++i)
    {
        cin >> g >> d;
        czas = d*droga.second + g*droga.first;
        if (czas < minimum)
        {
            liczba = 1;
            minimum = czas;
        }
        else if (czas == minimum)
            liczba++;
    }
    cout << minimum << ' ' << liczba;
}