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
#include<cstdio>
#include<algorithm>
#include<queue>

using namespace std;

static bool nieb[2000][2000];
static int odl[2000][2000];

typedef unsigned long long ull;

static ull czasy[1000000];

struct pole{
    int x, y;
    int d;

    bool operator<(pole a)const{
        return d > a.d;
    }
};

int main(){
    int n, m, k;
    scanf("%i%i%i", &n, &m, &k);

    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j){
            char z;
            scanf(" %c", &z);

            if(z == 'X'){
                nieb[i][j] = true;
            }
        }
    }

    priority_queue<pole> kolejka;

    pole p;
    p.x = 0;
    p.y = 0;
    p.d = 1;
    kolejka.push(p);

    while(!kolejka.empty()){
        pole mai = kolejka.top();
        kolejka.pop();

        int x = mai.x;
        int y = mai.y;
        int d = mai.d;

        if(odl[x][y] || nieb[x][y]){
            continue;
        }

        odl[x][y] = d;

        if(x){
            p.x = x - 1;
            p.y = y;
            p.d = d + 1;
            kolejka.push(p);
        }
        if(x < n - 1){
            p.x = x + 1;
            p.y = y;
            p.d = d + 1;
            kolejka.push(p);
        }
        if(y){
            p.x = x;
            p.y = y - 1;
            p.d = d + 1;
            kolejka.push(p);
        }
        if(y < m - 1){
            p.x = x;
            p.y = y + 1;
            p.d = d + 1;
            kolejka.push(p);
        }
    }

    int wynik = odl[n - 1][m - 1] - 1;
    ull dol = (wynik - (m-1) - (n-1)) / 2;
    ull gora = wynik - dol;

    for(int i = 0; i < k; ++i){
        int a, b;
        scanf("%i%i", &a, &b);

        czasy[i] = gora * a + dol * b;
    }

    sort(czasy, czasy + k);

    int i = 1;

    for(; i < k; ++i){
        if(czasy[i] != czasy[0]){
            break;
        }
    }

    printf("%llu %i\n", czasy[0], i);
}