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

#define mp make_pair
#define fi first
#define se second

using namespace std;

bool p[2000][2000];
int r[2000][2000][2];
// 0 -> v
// 1 <- ^
char c;
int n, m, k;

queue<pair<int, int> >q;
long long a, b, xa, xb;

int main() {
  ios_base::sync_with_stdio(0);

  cin >> n >> m >> k;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cin >> c;
      if (c == 'X') {
        p[i][j] = 1;
      }
    }
  }

  q.push(mp(0, 0));
  while(!q.empty()) {
    a = q.front().fi;
    b = q.front().se;
    q.pop();

    if (a + 1 < n && p[a + 1][b] == 0
        && r[a + 1][b][0] == 0 && r[a + 1][b][1] == 0) {
      r[a + 1][b][0] = r[a][b][0] + 1;
      r[a + 1][b][1] = r[a][b][1];
      q.push(mp(a + 1, b));
    }

    if (a - 1 >= 0 && p[a - 1][b] == 0
        && r[a - 1][b][0] == 0 && r[a - 1][b][1] == 0 && (a != 1 || b != 0)) {
      r[a - 1][b][0] = r[a][b][0];
      r[a - 1][b][1] = r[a][b][1] + 1;
      q.push(mp(a - 1, b));
    }

    if (b + 1 < m && p[a][b + 1] == 0
        && r[a][b + 1][0] == 0 && r[a][b + 1][1] == 0) {
      r[a][b + 1][0] = r[a][b][0] + 1;
      r[a][b + 1][1] = r[a][b][1];
      q.push(mp(a, b + 1));
    }

    if (b - 1 >= 0 && p[a][b - 1] == 0
        && r[a][b - 1][0] == 0 && r[a][b - 1][1] == 0 && (a != 0 || b != 1)) {
      r[a][b - 1][0] = r[a][b][0];
      r[a][b - 1][1] = r[a][b][1] + 1;
      q.push(mp(a, b - 1));
    }
  }

  xa = r[n - 1][m - 1][0];
  xb = r[n - 1][m - 1][1];

  cin >> a >> b;
  k--;
  long long res = a * xa + b * xb;
  int l = 1;

  while(k--) {
    cin >> a >> b;
    long long curr = a * xa + b * xb;
    if (curr == res) {
      l++;
    }
    if (curr < res) {
      res = curr;
      l = 1;
    }
  }

  cout << res << " " << l << endl;

  return 0;
}