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

using namespace std;

int main(){

    int m,n,k;
    scanf("%d %d %d", &n, &m,&k);

    static bool mapa[2001][2001]={};
    static bool visited[2001][2001]={};

    for(int row = 0; row<n;row++){
        string str;
        cin>>str;
        for(int col=0; col<m;col++)
            if(str[col]=='.')
                mapa[row][col]=1;
    }

    /*for(int i =0; i<n; i++){
        for(int j = 0; j<m; j++)
            cout<<mapa[i][j];
        cout<<endl;
    }*/

    static pair<long long, long long> dystans[2001][2001];//wypełnij dystansami po 10^7     [up][down]

    queue<int> q;
    q.push(0);
    while(!q.empty()){
        int ind = q.front();
        q.pop();
        int col=ind%m;
        int row=ind/m;
        int dcol[]={0,0,-1,1};
        int drow[]={1,-1,0,0};
        for(int i=0;i<4;i++){
            int ncol=col+dcol[i];
            int nrow=row+drow[i];
            pair<long long,long long> current = dystans[row][col];
//cout<<"("<<ind<<")";
            if(ncol<m && ncol>=0 && nrow<n && nrow>=0 && !visited[nrow][ncol] && mapa[nrow][ncol]){
                if(dcol[i]+drow[i]>0)//w górę
                    dystans[nrow][ncol]=make_pair(current.first+1,current.second);
                if(dcol[i]+drow[i]<0)//w dół
                    dystans[nrow][ncol]=make_pair(current.first,current.second+1);
                visited[nrow][ncol]=1;
                q.push(nrow*m+ncol);
            }
        }
    }

//printf("%d up %d down\n", dystans[n-1][m-1].first,dystans[n-1][m-1].second);
    long long distUp=dystans[n-1][m-1].first;
    long long distDown=dystans[n-1][m-1].second;

    int upSpeed[k],downSpeed[k];
    for(int i=0;i<k;i++)
        scanf("%d %d",&upSpeed[i],&downSpeed[i]);

    long long minTime = upSpeed[0]*distUp+downSpeed[0]*distDown;
    int amount=0;
    for(int i=0;i<k;i++){
        long long time=upSpeed[i]*distUp+downSpeed[i]*distDown;
        if(time<minTime){
            amount = 1;
            minTime=time;
        }
        else if(time==minTime)
            amount++;
    }
    printf("%lld %d\n", minTime, amount);

    return 0;

}