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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1 << 29;
const char X = 'X';
const char R = 'R';

struct point {
  int x, y;
  pair<ll,ll> steps;

  point(int _x, int _y, pair<ll,ll> _s) : x(_x), y(_y), steps(_s) {}
  point() {}
};

vector<pair<ll,ll>> bfs(vector<vector<char>> &adj) {
  queue<point> Q;
  const int n = adj.size()-2, m = adj[0].size()-2;
  Q.push(point(1, 1, {0, 0}));
  adj[1][1] = X;
  adj[n][m] = R;


  pair<ll,ll> res1 = {INF, INF}, res2 = res1;
  while (!Q.empty()) {
    auto v = Q.front();
    Q.pop();

    if (adj[v.x+1][v.y] != X) {
      if (adj[v.x+1][v.y] == R) {
        res1 = {v.steps.first+1, v.steps.second};
        swap(res1, res2);
      }
      else {
        adj[v.x+1][v.y] = X; 
        Q.push(point(v.x+1, v.y, {v.steps.first+1, v.steps.second}));
      }
    }
    if (adj[v.x-1][v.y] != X) {
      adj[v.x-1][v.y] = X; Q.push(point(v.x-1, v.y, {v.steps.first, v.steps.second+1}));
    }
    if (adj[v.x][v.y+1] != X) {
      if (adj[v.x][v.y+1] == R) {
        res1 = {v.steps.first+1, v.steps.second};
        swap(res1, res2);
      }
      else {
        adj[v.x][v.y+1] = X; 
        Q.push(point(v.x, v.y+1, {v.steps.first+1, v.steps.second}));
      }
    }
    if (adj[v.x][v.y-1] != X) {
      adj[v.x][v.y-1] = X; Q.push(point(v.x, v.y-1, {v.steps.first, v.steps.second+1}));
    }
  }

  return {res1, res2};
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  int n, m, k; cin >> n >> m >> k;
  vector<vector<char>> G(m+2, vector<char>(n+2, X));

  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      cin >> G[j][i];
    }
  }

  auto p = bfs(G);

  int cnt = 0;
  ll mn = 1e16;
  while (k--) {
    ll a, b; cin >> a >> b;
    ll steps = min(a*p[0].first + b*p[0].second, a*p[1].first + b*p[1].second);
    if (steps < mn) {
      mn = steps; cnt = 1;
    }
    else cnt += steps == mn;
  }

  cout << mn << ' ' << cnt;
}