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
#include <bits/stdc++.h>
using namespace std;
#define PB push_back
string mapa[2000];
typedef long long int ll;
typedef pair<ll,ll> PLL;
vector<PLL> v;
ll n, m, k;
ll dist[2000][2000];
ll xs[] = {0, 1, 0, -1};
ll ys[] = {1, 0, -1, 0};
const ll INF = LLONG_MAX/3;
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m>>k;
	for(int i = 0; i < n; ++i) {
		cin>>mapa[i];
	}
	ll f, s;
	for(int i = 0; i < k; ++i) {
		cin>>f>>s;
		v.PB({f, s});
	}
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < m; ++j) {
			dist[i][j] = INF;
		}
	}
	queue<PLL> q;
	q.push({0, 0});
	dist[0][0] = 0;
	while(!q.empty()) {
		auto cur_vertex = q.front(); q.pop();
		auto x = cur_vertex.first;
		auto y = cur_vertex.second;
		for(int i = 0; i < 4; ++i) {
			auto nx = x + xs[i];
			auto ny = y + ys[i];
			if(nx < 0 || ny < 0 || nx >= n || ny >= m)
				continue;
			if(mapa[nx][ny] == 'X') 
				continue;
			if(dist[x][y] + 1 < dist[nx][ny] && i < 2) {
				dist[nx][ny] = dist[x][y] + 1;
				q.push({nx, ny});
			}
			else if(dist[x][y] < dist[nx][ny] && i >= 2) {
				dist[nx][ny] = dist[x][y];
				q.push({nx, ny});
			}
		}
	}
	
	ll sum = dist[n-1][m-1];
	ll mini = INF;
	ll cnt = 0;
	for(auto p : v) {
		ll calc = (p.first + p.second)*sum - p.second*(n+m-2);
		//cout<<calc<<"\n";
		if(calc < mini) {
			mini = calc;
			cnt = 1;
		} else if (calc == mini) {
			cnt++;
		}
	}
	cout<<mini<<" "<<cnt<<"\n";
	return 0;
}