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
#include <iostream>
#include <limits>
#include <queue>

using namespace std;

int m,n,k;
bool mapa[2000][2000];
int dist[2000][2000];
int a[1000000];
int b[1000000];

int main()
{
    cin.sync_with_stdio(0);
    cin >> n >> m >> k;
    for(int y=0; y<n; ++y)
    {
        for(int x=0; x<m; ++x)
        {
            char c;
            cin >> c;
            if(c=='.')
            {
                mapa[y][x] = true;
            }
        }
    }
    for(int i=0; i<k; ++i)
    {
        cin >> a[i] >> b[i];
    }

    for(int y=0; y<n; ++y)
    {
        for(int x=0; x<m; ++x)
        {
            dist[y][x] = 1'000'000'000;
        }
    }
    dist[0][0] = 0;

    queue<pair<int,int>> q;
    q.push(make_pair(0,0));
    while(!q.empty())
    {
        pair<int,int> pos = q.front();
        q.pop();
        if(!mapa[pos.first][pos.second])
        {
            continue;
        }
        int adj[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
        for(int i=0; i<4; ++i)
        {
            int new_y = pos.first  + adj[i][0];
            int new_x = pos.second + adj[i][1];
            if(new_x<0 || new_y<0 || new_x>=m || new_y>=n || !mapa[new_y][new_x])
            {
                continue;
            }
            dist[new_y][new_x] = min(dist[new_y][new_x],dist[pos.first][pos.second]+1);
            q.push(make_pair(new_y,new_x));
        }
        mapa[pos.first][pos.second] = false;
    }

    long long int best_time = numeric_limits<long long int>::max();
    int people_count = 0;
    for(int i=0; i<k; ++i)
    {
        long long int base_steps = (n+m-2);
        long long int extra_2steps = (dist[n-1][m-1]-(n+m-2))/2;
        long long int new_time = a[i]*base_steps + (a[i]+b[i])*extra_2steps;
        if(new_time<best_time)
        {
            best_time = new_time;
            people_count = 1;
        }
        else if(new_time==best_time)
        {
            people_count++;
        }
    }
    cout << best_time << " " << people_count;

    return 0;
}