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
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

char s[2013][2013];
int d[2013][2013];

int xx[4] = {-1, 1, 0, 0};
int yy[4] = {0, 0, -1, 1};

int main() {
  int n,m,k;
	scanf("%d %d %d",&n,&m,&k);
	for (int i = 0; i < n; i++) scanf("%s", s[i]);
	vector<int> q(1);
	for (int i = 0; i < n; i++) for(int j = 0; j < m; j++) d[i][j] = 0;
	d[0][0] = 1;
	for  (int qq = 0; qq < q.size(); ++qq) {
		int i = q[qq] / m;
		int j = q[qq] % m;
		for (int z = 0; z < 4; z++) {
			int a = i+xx[z];
			int b = j+yy[z];
			if (a < 0 || a>=n || b < 0 || b >= m) continue;
			if (s[a][b] != 'X' && !d[a][b]) {
				d[a][b] = d[i][j] + 1;
				q.push_back(a * m + b);
			}
		}
	}
	int od = d[n-1][m-1]-1;
	long long B = (od-n-m+2) / 2;
	long long A = od - B;
	long long ret = 1LL<<61;
	int cnt = 0;
	for (int i = 0; i < k; i++) {
		int a,b;
		scanf("%d %d",&a,&b);
		long long w = a*A+b*B;
		if (w < ret) {
			ret = w;
			cnt = 0;
		}
		if (w == ret) cnt++;
	}
	printf("%lld %d\n",ret,cnt);
	return 0;
}