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

#define N 2000

int t[N][N];
std::queue <std::pair <int, int>> q;

int main ()
{
  int n, m, k;
  scanf ("%i%i%i", &n, &m, &k);
  for (int i=0; i<n; i++) for (int j=0*scanf(" "); j<m; j++) t[i][j] = getchar()=='.'? N*N: -1;
  t[0][0] = 0;
  q.push({0, 0});
  while (!q.empty())
  {
    auto [i, j] = q.front(); q.pop();
    for (auto [x, y]: (int [][2]){{i+1, j}, {i, j+1}, {i-1, j}, {i, j-1}})
    if (0<=x && x<n && 0<=y && y<m && t[x][y] > t[i][j]+1) t[x][y] = t[i][j]+1, q.push({x, y});
  }
  int g = (t[n-1][m-1] + (n-1+m-1))/2;
  int d = (t[n-1][m-1] - (n-1+m-1))/2;
  long long x = 1e18;
  int y = 0;
  while (k--)
  {
    int a, b;
    scanf ("%i%i", &a, &b);
    long long c = 1LL*a*g + 1LL*b*d;
    if (c<x) x = c, y = 0;
    if (c==x) y++;
  }
  printf ("%lli %i\n", x, y);
  return 0;
}