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

using namespace std;

const int inf = 2000000000;

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);

    int m, n, k;

    cin >>n>>m>>k;

    vector<vector<int >> tab ( n+2,  vector<int>(m+2, -1) );

    for (int y=1; y<=n; y++){
        for (int x=1; x<=m; x++){
            char c;
            cin>>c;
            if (c=='X')
                tab[y][x]=-1;
            else
                tab[y][x]=inf;
        }
    }

    queue<tuple<int, int, int>> Q;
    Q.push(make_tuple(1,1,-1));


    while (!Q.empty()){
        int y,x, s;
        tie(y,x,s) = Q.front();
        Q.pop();
        if ((tab[y][x] >=0 ) ){ // dozwolony
            if (tab[y][x] > s+1 ){
                tab[y][x] = s+1;

                Q.push(make_tuple(y+1,x,s+1 ));
                Q.push(make_tuple(y-1,x,s+1 ));
                Q.push(make_tuple(y,x+1,s+1 ));
                Q.push(make_tuple(y,x-1,s+1 ));
            }
        }
    }

    int length = tab[n][m] ;

    int64_t optimal_length = m+n-2;

    int64_t loops = (length - optimal_length)/2;

    int64_t record=numeric_limits<int64_t>::max();
    int n_winners=0;

    while (k-->0){
        int a,b;
        cin>>a>>b;
        int64_t time = a*optimal_length + (a+b)*loops;
        if (time < record ) {
            record = time;
            n_winners = 1;
        }else if(time == record){
            n_winners++;
        }
    }

    cout<<record<<" "<<n_winners<<endl;

    return 0;
}