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
89
90
91
92
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
typedef pair <int, int> pii;
typedef long long ll;
typedef double db;

const int N = 2000;
const int K = 1000000;
const ll INF = 1e18;
const int dx1[] = {1, 0};
const int dy1[] = {0, 1};
const int dx2[] = {-1, 0};
const int dy2[] = {0, -1};

int n, m, k;
ll res = INF, cnt, a, b, c, d, t;
char plane[N + 5][N + 5];
pii dis[N + 5][N + 5];
bool visited[N + 5][N + 5];
queue <pii> q;

void Bfs(pii v){
	q.push(v);
	visited[v.fi][v.se] = true;
	while(!q.empty()){
		pii u = q.front();
		pii d = dis[u.fi][u.se];
		q.pop();
		for(int i=0; i<2; i++){
			int x = u.fi + dx1[i];
			int y = u.se + dy1[i];
			if(!visited[x][y] and plane[x][y] != 'X'){
				visited[x][y] = true;
				dis[x][y] = d;
				dis[x][y].fi ++;
				q.push({x, y});
			}
		}
		for(int i=0; i<2; i++){
			int x = u.fi + dx2[i];
			int y = u.se + dy2[i];
			if(!visited[x][y] and plane[x][y] != 'X'){
				visited[x][y] = true;
				dis[x][y] = d;
				dis[x][y].se ++;
				q.push({x, y});
			}
		}
	}	
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);	
	
	cin >> n >> m >> k;
	for(int i=0; i<=n+1; i++){
		plane[i][0] = 'X';
		plane[i][m + 1] = 'X';
	}
	for(int i=0; i<=m+1; i++){
		plane[n + 1][i] = 'X';
		plane[0][i] = 'X';
	}
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			cin >> plane[i][j];
		}
	}
	Bfs({1, 1});
	c = dis[n][m].fi;
	d = dis[n][m].se;
	while(k --){
		cin >> a >> b;
		t = a * c + b * d;
		if(t == res){
			cnt ++;
		}
		if(t < res){
			res = t;
			cnt = 1;
		}
	}
	cout << res << " " << cnt << "\n";
	 
	return 0;
}