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

#define ll long long

const ll INF = 8001002003001002003LL;

using namespace std;

int pr[2111][2111];
char d[2111][2111];
ll t[2][1234567];
int mv[][2] = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
int inv[][2] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
int up, down;
int n,m;

void findPath() {
  int x,y;
  set<pair<int, int> > vis;
  queue<pair<int, int> > q;

  pair<int, int> start(0,0);
  vis.insert(start);
  q.push(start);
  while(!q.empty()) {
    pair<int, int> p = q.front();
    q.pop();
    int x = p.first;
    int y = p.second;
    for(int i=0;i<4;i++) {
      int cx = x + mv[i][0];
      int cy = y + mv[i][1];
      if(cx >= 0 && cx < m && cy >= 0 && cy < n && d[cy][cx]=='.') {
        pair<int, int> next(cx, cy);
        auto it = vis.find(next);
        if(it == vis.end()) {
          vis.insert(next);
          q.push(next);
          pr[cy][cx] = i;
        }
      }
    }
  }
}

void countSteps() {
  pair<int, int> cur(m-1,n-1);
  while(cur.first > 0 || cur.second > 0) {
    int i = pr[cur.second][cur.first];
    cur.first += inv[i][0];
    cur.second += inv[i][1];
    if((i == 0) || (i == 2)) {
      down++;
    } else {
      up++;
    }
  }
}

int main(int argc, char** argv) {
  int k;
  scanf("%d%d%d",&n,&m,&k);
  for(int i=0;i<n;i++) {
    scanf("%s", &(d[i]));
  }
  for(int i=0;i<k;i++) {
    scanf("%lld%lld", &(t[0][i]), &(t[1][i]));
  }

  findPath();
  countSteps();

  ll min = INF;
  int cnt = 0;
  for(int i=0;i<k;i++) {
    ll time = t[0][i] * up + t[1][i] * down;
    if(time < min) {
      min = time;
      cnt = 1;
    } else if(time == min) {
      cnt++;
    }
  }
  printf("%lld %d\n",min,cnt);
  return 0;
}