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
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;

int n, m, k;
int vis[2009][2009], dis[2009][2009];
char c[2009][2009];
ll a[1000009], b[1000009];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

    cin >> n >> m >> k;

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> c[i][j];
        }
    }

    dis[1][1] = 0;
    vis[1][1] = 1;
    queue<pii> Q;
    Q.push({1, 1});
    while (!Q.empty())
    {
        int x = Q.front().fi;
        int y = Q.front().se;
        Q.pop();

        if (x + 1 <= n && vis[x + 1][y] == 0 && c[x + 1][y] == '.')
        {
            vis[x + 1][y] = 1;
            dis[x + 1][y] = dis[x][y] + 1;
            Q.push({x + 1, y});
        }

        if (y + 1 <= m && vis[x][y + 1] == 0 && c[x][y + 1] == '.')
        {
            vis[x][y + 1] = 1;
            dis[x][y + 1] = dis[x][y] + 1;
            Q.push({x, y + 1});
        }

        if (1 <= x - 1 && vis[x - 1][y] == 0 && c[x - 1][y] == '.')
        {
            vis[x - 1][y] = 1;
            dis[x - 1][y] = dis[x][y] + 1;
            Q.push({x - 1, y});
        }

        if (1 <= y - 1 && vis[x][y - 1] == 0 && c[x][y - 1] == '.')
        {
            vis[x][y - 1] = 1;
            dis[x][y - 1] = dis[x][y] + 1;
            Q.push({x, y - 1});
        }
    }

    dis[n][m] -= n + m - 2;
    dis[n][m] /= 2;

    ll mn = LLONG_MAX;
    int cnt = 0;
    for (int i = 1; i <= k; i++)
    {
        cin >> a[i] >> b[i];

        mn = min(mn, a[i] * (ll)(n + m - 2) + (a[i] + b[i]) * (ll)dis[n][m]);
    }
    for (int i = 1; i <= k; i++)
    {
        if (mn == a[i] * (ll)(n + m - 2) + (a[i] + b[i]) * (ll)dis[n][m]) cnt++;
    }

    cout << mn << " " << cnt << "\n";
}