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
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define ull unsigned long long int

using namespace std;

int n, m, k;

int idx(int i, int j) {
    return i*m + j;
}

int main() {
    char field;

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

    bool *traps = new bool[n*m]();
    int *steps_up = new int[n*m]();
    int *steps_down = new int[n*m]();

    bool *visited = new bool[n*m]();
    int *exti = new int[2*n*m]();
    int *extj = new int[2*n*m]();

    int *A = new int[k]();
    int *B = new int[k]();
    
    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
            scanf(" %c", &field);
            if(field=='X') {
                traps[idx(i,j)] = true;
            }
        }
    }
    
    for(int i=0; i<k; i++) {
        scanf("%d %d", A+i, B+i);
    }

    exti[0] = n-1;
    extj[0] = m-1;
    visited[idx(n-1, m-1)] = true;
    int curr = 1, next = 0;
    int row = 0, rowcurr, rownext;
    int i, j, idxcurr, idxnext;
    while(true) {
        rowcurr = row*n*m;
        rownext = (1-row)*n*m;
        for(int c=0; c<curr; c++) {
            i = exti[rowcurr+c];
            j = extj[rowcurr+c];
            idxcurr = idx(i,j);

            if(i-1 >= 0) {
                idxnext = idx(i-1, j);
                if(!visited[idxnext]) {
                    if(idxnext == 0) {
                        steps_up[idxnext] = steps_up[idxcurr]+1;
                        steps_down[idxnext] = steps_down[idxcurr];
                        goto complete;
                    }
                    if(!traps[idxnext]) {
                        steps_up[idxnext] = steps_up[idxcurr]+1;
                        steps_down[idxnext] = steps_down[idxcurr];
                        exti[rownext+next] = i-1;
                        extj[rownext+next] = j;
                        next++;
                    }
                    visited[idxnext] = true;
                }
            }
            if(j-1 >= 0) {
                idxnext = idx(i, j-1);
                if(!visited[idxnext]) {
                    if(idxnext == 0) {
                        steps_up[idxnext] = steps_up[idxcurr]+1;
                        steps_down[idxnext] = steps_down[idxcurr];
                        goto complete;
                    }
                    if(!traps[idxnext]) {
                        steps_up[idxnext] = steps_up[idxcurr]+1;
                        steps_down[idxnext] = steps_down[idxcurr];
                        exti[rownext+next] = i;
                        extj[rownext+next] = j-1;
                        next++;
                    }    
                    visited[idxnext] = true;
                }
            }
            if(i+1 < n) {
                idxnext = idx(i+1, j);
                if(!visited[idxnext]) {
                    if(!traps[idxnext]) {
                        steps_up[idxnext] = steps_up[idxcurr];
                        steps_down[idxnext] = steps_down[idxcurr]+1;
                        exti[rownext+next] = i+1;
                        extj[rownext+next] = j;
                        next++;
                    }    
                    visited[idxnext] = true;
                }
            }
            if(j+1 < m) {
                idxnext = idx(i, j+1);
                if(!visited[idxnext]) {
                    if(!traps[idxnext]) {
                        steps_up[idxnext] = steps_up[idxcurr];
                        steps_down[idxnext] = steps_down[idxcurr]+1;
                        exti[rownext+next] = i;
                        extj[rownext+next] = j+1;
                        next++;
                    }    
                    visited[idxnext] = true;
                }
            }
        }
        row = (row+1)%2;
        curr = next;
        next = 0;
    }
    complete:;

    ull best=ULLONG_MAX, player;
    int count=0;

    for(int i=0; i<k; i++) {
        player = (ull)A[i] * (ull)steps_up[0] + (ull)B[i] * (ull)steps_down[0];
        if(player == best) {
            count++;
        }
        else if(player < best) {
            best = player;
            count = 1; 
        }
    }

    printf("%llu %d", best, count);

    delete [] traps;
    delete [] steps_up;
    delete [] steps_down;
    delete [] visited;
    delete [] exti;
    delete [] extj;
    delete [] A;
    delete [] B;

    return 0;
}