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
#include<bits/stdc++.h>
using namespace std;
bool visited[2007][2007];
char t[2007][2007];
long long o[2007][2007], n, m, k, odl;
int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m >> k;
  for(long long i = 0;i < n;i++)
    for(long long j = 0;j < m;j++)
      cin >> t[i][j];

  queue<tuple<int, long long>> q;
  q.emplace(0, 0);
  while(!q.empty()){
    long long a, b;
    tie(a, b) = q.front();
    q.pop();
    visited[a][b] = 1;
    if(a > 0 && !visited[a - 1][b] && t[a - 1][b] == '.'){
      q.emplace(a - 1, b);
      o[a - 1][b] = o[a][b] + 1;
      visited[a - 1][b] = 1;
    }
    if(a < n - 1 && !visited[a + 1][b] && t[a + 1][b] == '.'){
      q.emplace(a + 1, b);
      o[a + 1][b] = o[a][b] + 1;
      visited[a + 1][b] = 1;
    }
    if(b > 0 && !visited[a][b - 1] && t[a][b - 1] == '.'){
      q.emplace(a, b - 1);
      o[a][b - 1] = o[a][b] + 1;
      visited[a][b - 1] = 1;
    }
    if(b < m - 1 && !visited[a][b + 1] && t[a][b + 1] == '.'){
      q.emplace(a, b + 1);
      o[a][b + 1] = o[a][b] + 1;
      visited[a][b + 1] = 1;
    }
  }
  odl = o[n - 1][m - 1];

  long long Maks = LLONG_MAX, Knust = 0;
  for(long long i = 0, a, b;i < k;i++){
    cin >> a >> b;
    long long w = (n + m - 2) * a + (odl - n - m + 2) / 2 * (a + b);
    if(Maks > w){
      Maks = w;
      Knust = 0;
    }
    if(Maks == w)
      Knust++;
  }
  cout << Maks << ' ' << Knust;
}