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
#include <bits/stdc++.h>

using namespace std;

char mapa[2005][2005];

int odwiedzony[2005][2005];

vector<pair<int, int> > kierunki = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};

void bfs(){
    odwiedzony[1][1] = 1;
    vector<pair<int, int> > kolejka = {{1, 1}};
    for (int i = 0; i < (int)kolejka.size(); i++){
        pair<int, int> xd = kolejka[i];
        for (pair<int, int> j : kierunki){
            int x = xd.first + j.first, y = xd.second + j.second;
            if (!odwiedzony[x][y] && mapa[x][y] == '.'){
                odwiedzony[x][y] = odwiedzony[xd.first][xd.second] + 1;
                kolejka.emplace_back(x, y);
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    long long n, m, q, wynik = 1e18, ile = 0, a, b;
    cin >> n >> m >> q;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> mapa[i][j];
    bfs();
    while (q--){
        cin >> a >> b;
        long long xd = (odwiedzony[n][m] - (m - 1) - (n - 1) - 1) / 2;
        long long pom = (long long)((long long)a * ((long long)((m - 1) + (n - 1))) + (long long)(b + a) * xd);
        if (wynik > pom){
            wynik = pom;
            ile = 0;
        }
        if (wynik == pom)
            ile++;
    }
    cout << wynik << " " << ile << "\n";
    return 0;
}