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
#include <bits/stdc++.h>
using namespace std;
char dane[2002][2002];
int ta[2002][2002],tb[2002][2002],vis[2002][2002];

void bfs(unsigned int i,unsigned int j)
{
  vis[i][j]=1; 
  queue<int> kolx,koly;
  kolx.push(i);
  koly.push(j); 
  while(!kolx.empty())
  {
  unsigned int i=kolx.front();  kolx.pop();                  
  unsigned int j=koly.front(); koly.pop();
  if(dane[i-1][j]=='.' && vis[i-1][j]==0) 
                      {
                      vis[i-1][j]=1;                                                  
                      kolx.push(i-1);
                      koly.push(j);  
                      tb[i-1][j] = tb[i][j]+1;
					  ta[i-1][j] = ta[i][j];                                            
                      }                  
  if(dane[i+1][j]=='.'  && vis[i+1][j]==0) 
                      {
                      vis[i+1][j]=1;                                                  
                      kolx.push(i+1);
                      koly.push(j);  
                      tb[i+1][j] = tb[i][j];
					  ta[i+1][j] = ta[i][j] + 1;                                        
                      } 
  if(dane[i][j-1]=='.'  && vis[i][j-1]==0) 
                      {
                      vis[i][j-1]=1;                                                  
                      kolx.push(i);
                      koly.push(j-1);  
                      tb[i][j-1] = tb[i][j]+1;
					  ta[i][j-1] = ta[i][j];                                               
                      } 
  if(dane[i][j+1]=='.'  && vis[i][j+1]==0) 
                      {
                      vis[i][j+1]=1;                                                  
                      kolx.push(i);
                      koly.push(j+1);  
                      tb[i][j+1] = tb[i][j];
					  ta[i][j+1] = ta[i][j] +1;                       
                      } 
  }                  
 }

int main() {
ios_base::sync_with_stdio(0);
int n, m ,k, i, j,ilosc = 1;
long long czas, mini , a, b;
cin >> n >> m >> k;
for(i = 0;i <= n+ 1; i++) dane[i][0] = dane[i][m+1] = 'X';
for(j = 0;j <= m + 1; j++) dane[0][j] = dane[n+1][j] = 'X';
for(i = 1; i <= n; i++) 
	for(j = 1; j <= m; j++ )cin >> dane[i][j];
bfs(1,1);
cin >> a >> b;
mini = ta[n][m] * a + tb[n][m] * b;
k--;
while(k--){
	cin >> a >> b;
	czas = ta[n][m] * a + tb[n][m] * b;
	//cout << czas << endl;
	if(czas < mini) {
		mini = czas;
		ilosc = 1;
	}
	else if (czas == mini) ilosc++;
	
}
cout << mini <<" "<<ilosc << endl;
/*
for(i = 0; i <= n+1; i++) {
	for(j = 0; j <= m+1; j++ ) cout << dane[i][j]<<" "; cout << endl;
}
for(i = 0; i <= n+1; i++) {
	for(j = 0; j <= m+1; j++ ) cout << ta[i][j]<<" "; cout << endl;
}
for(i = 0; i <= n+1; i++) {
	for(j = 0; j <= m+1; j++ ) cout << tb[i][j]<<" "; cout << endl;
}
*/	
	return 0;
}