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
#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;

const int N = ((int)(2e3))+50;
const long long INF = ((long long)(1e18))+50;

struct metadata{
	int x;
	int y;
	int left;
	int right;
	int up;
	int down;
};

int n,m,k;
char tab[N][N];
bool met[N][N];
long long d;
vector<metadata> answers;
vector< pair <long long, long long > > params;

void bfs(int p, int k){
	queue < metadata > Q;
	met[p][k] = 1;
	Q.push( { 1 , 1 , 0 , 0 , 0 , 0 } );
	while(!Q.empty()){
		metadata data = Q.front();
		Q.pop();
		metadata newData = data;
		int x = data.x;
		int y = data.y;
		if((x == n) && (y == m)) d = data.left + data.right + data.up + data.down;
		newData = data;
		if( !met[x+1][y] && ( tab[x+1][y] == '.' ) ) newData.x+=1, newData.down++, met[newData.x][newData.y] = 1, Q.push(newData);
		newData = data;
		if( !met[x-1][y] && ( tab[x-1][y] == '.' ) ) newData.x-=1, newData.up++, met[newData.x][newData.y] = 1, Q.push(newData);
		newData = data;
		if( !met[x][y+1] && ( tab[x][y+1] == '.' ) ) newData.y+=1, newData.right++, met[newData.x][newData.y] = 1, Q.push(newData);
		newData = data;
		if( !met[x][y-1] && ( tab[x][y-1] == '.' ) ) newData.y-=1, newData.left++, met[newData.x][newData.y] = 1, Q.push(newData);
	}
}

int main(){
	ios_base::sync_with_stdio( 0 ); cin.tie( 0 ); cout.tie( 0 );
	cin>>n>>m>>k;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= m; j++){
			cin>>tab[i][j];
		}		
	}
	long long t1,t2;
	for (int i = 0; i < k; i++){
		cin>>t1>>t2;
		params.push_back({t1,t2});
	}
	long long ans = INF;
	long long cnt = 0;
	bfs(1,1);
	for (int i = 0; i < (int)params.size(); i++){
		long long a = params[i].s;
		long long b = params[i].f;
		long long sum = (d - n - m + 2) / 2;
		long long t = b*(m+n) + b*(sum) + a*(sum) - 2*b;	
		if( ans > t ){
			ans = t;
			cnt = 1;
		} else if( ans == t ){
			cnt++;
		}
	}
	cout<<ans<<" "<<cnt<<endl;
}