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
#include <bits/stdc++.h>
#define magiczne ios_base::sync_with_stdio(0);
#define linijki cin.tie(NULL);

using namespace std;

bool odw[2001][2001];
char mapa[2001][2001];

int main()
{
    magiczne linijki
	queue <long long int> sto;
	queue <int> nka;
	queue <int> mka;
	vector <long long int> wyniki;
	long long int mini=LLONG_MAX;
	long long int m, n, k;
	long long int a, b, desc, asc, odp=0;
	cin>>n>>m>>k;
	for(int c=0;c<n;c++)
	{
		for(int d=0;d<m;d++)
		{
			cin>>mapa[c][d];
		}
	}
	odw[0][0]=1;
	sto.push(0);
	nka.push(0);
	mka.push(0);
	while(1)
	{
		if(nka.front()==n-1 && mka.front()==m-1) break;
		if(nka.front()!=0)
		{
			if(mapa[nka.front()-1][mka.front()]=='.' && odw[nka.front()-1][mka.front()]==0)
			{
				sto.push(sto.front()+1);
				nka.push(nka.front()-1);
				mka.push(mka.front());
				odw[nka.front()-1][mka.front()]=1;
			}
		}
		if(nka.front()!=n-1)
		{
			if(mapa[nka.front()+1][mka.front()]=='.' && odw[nka.front()+1][mka.front()]==0)
			{
				sto.push(sto.front()+1);
				nka.push(nka.front()+1);
				mka.push(mka.front());
				odw[nka.front()+1][mka.front()]=1;
			}
		}
		if(mka.front()!=0)
		{
			if(mapa[nka.front()][mka.front()-1]=='.' && odw[nka.front()][mka.front()-1]==0)
			{
				sto.push(sto.front()+1);
				nka.push(nka.front());
				mka.push(mka.front()-1);
				odw[nka.front()][mka.front()-1]=1;
			}	
		}
		if(mka.front()!=m-1)
		{
			if(mapa[nka.front()][mka.front()+1]=='.' && odw[nka.front()][mka.front()+1]==0)
			{
				sto.push(sto.front()+1);
				nka.push(nka.front());
				mka.push(mka.front()+1);
				odw[nka.front()][mka.front()+1]=1;
			}
		}
		sto.pop();
		mka.pop();
		nka.pop();
	}
	desc=(sto.front()-m-n+2)/2;
	asc=sto.front()-desc;
	//cout<<asc<<" "<<desc<<"\n";
	for(int c=0;c<k;c++)
	{
		cin>>a>>b;
		mini=min(mini, a*asc+b*desc);
		wyniki.push_back(a*asc+b*desc);
	}
	for(int c=0;c<wyniki.size();c++) if(wyniki[c]==mini) odp++;
	cout<<mini<<" "<<odp;
    return 0;
}