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
#include <iostream>
   #include <stdio.h>
   using namespace std;
   #include <cstdio>

  int getNumber() {
    int number = 0;
    int letter;
    do {
      letter = getchar();
    } while (letter <= 32);
    number = letter - '0';

    while (true) {
      letter = getchar();
      if (letter <= 32) {
        break;
      }
      number = number * 10 + (letter - '0');
    }
    return number;
  }

  int getContent() {
    int c;
    do {
      c = getchar();
    } while (c <= 32);
    return c;
  }

  const int MAX_N_M = 2005;

  int n, m, k;
  int map[MAX_N_M][MAX_N_M];

  int FREE = 0;
  int BLOCKED = 1;
  int X = 0;
  int Y = 1;

  int queue[MAX_N_M * MAX_N_M][2];
  int queueStart = 0;
  int queueSize = 0;

  void putIfFree(int x, int y) {
    if (map[x][y] == FREE) {
      queue[queueStart + queueSize][X] = x;
      queue[queueStart + queueSize][Y] = y;
      queueSize++;
    }
  }

  int main() {
    n = getNumber();
    m = getNumber();
    k = getNumber();

    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        int cell = getContent();
        if (cell == 'X') {
          map[i][j] = BLOCKED;
        } else if (cell == '.') {
          map[i][j] = FREE;
        } else {
          return -1;
        }
      }
    }

    int distance[MAX_N_M][MAX_N_M];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        distance[i][j] = 2000000000;
      }
    }

    putIfFree(0, 0);
    distance[0][0] = 0;

    while (queueSize > 0) {
      int x = queue[queueStart][X];
      int y = queue[queueStart][Y];
      queueStart++;
      queueSize--;

      int myCost = distance[x][y];
      int myExtraCost = myCost + 1;

      // left
      if (x > 0) {
        int neighborCost = distance[x - 1][y];
        if (myExtraCost < neighborCost) {
          distance[x - 1][y] = myExtraCost;
          putIfFree(x - 1, y);
        }
      }
      // right
      if (x < n) {
        int neighborCost = distance[x + 1][y];
        if (myExtraCost < neighborCost) {
          distance[x + 1][y] = myExtraCost;
          putIfFree(x + 1, y);
        }
      }
      // up
      if (y > 0) {
        int neighborCost = distance[x][y - 1];
        if (myExtraCost < neighborCost) {
          distance[x][y - 1] = myExtraCost;
          putIfFree(x, y - 1);
        }
      }
      // down
      if (y < m) {
        int neighborCost = distance[x][y + 1];
        if (myExtraCost < neighborCost) {
          distance[x][y + 1] = myExtraCost;
          putIfFree(x, y + 1);
        }
      }
    }
    int elevation = n + m - 2;
    int distanceToPeak = distance[n - 1][m - 1];
    int distanceDownhill = (distanceToPeak - elevation) / 2;
    int distanceUphill = distanceToPeak - distanceDownhill;

    long long shortestTime = -1;
    int numberOfWinners = 0;

    for (int i = 0; i < k; i++) {
      long long timeUp;
      cin >> timeUp;
      long long timeDown;
      cin >> timeDown;

      long long totalTime = timeUp * distanceUphill + timeDown * distanceDownhill;
      if (totalTime < shortestTime || shortestTime == -1) {
        shortestTime = totalTime;
        numberOfWinners = 1;
      } else if (totalTime == shortestTime) {
        numberOfWinners++;
      }
    }

    cout << shortestTime << " " << numberOfWinners;

    return 0;
  }