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
#include<bits/stdc++.h>

using namespace std;

const int MAXN=(int)2e3+99;

bool tab[MAXN][MAXN];
int n, m, k, odla[MAXN][MAXN], odlb[MAXN][MAXN], a[(int)1e6+99], b[(int)1e6+99], ile=0;
long long mini=(long long)1e18;

void dfs(int x, int y, int mina=0, int minb=0)
{
	//tab[x][y]=0;
	//mina=min(mina, odla[x][y]);
	//minb=min(minb, odlb[x][y]);
	odla[x][y]=mina;
	odlb[x][y]=minb;
	if(tab[x+1][y]&&odla[x+1][y]+odlb[x+1][y]>mina+1+minb) dfs(x+1, y, mina+1, minb);
	if(tab[x][y+1]&&odla[x][y+1]+odlb[x][y+1]>mina+1+minb) dfs(x, y+1, mina+1, minb);
	if(tab[x-1][y]&&odla[x-1][y]+odlb[x-1][y]>mina+1+minb) dfs(x-1, y, mina, minb+1);
	if(tab[x][y-1]&&odla[x][y-1]+odlb[x][y-1]>mina+1+minb) dfs(x, y-1, mina, minb+1);
}

void bfs(int x, int y)
{
	queue<pair<pair<int, int>, pair<int, int>>>q;
	int mina=0, minb=0;
	q.push({{x, y}, {mina, minb}});
	while(!q.empty())
	{
		x=q.front().first.first;
		y=q.front().first.second;
		mina=q.front().second.first;
		minb=q.front().second.second;
		q.pop();
		odla[x][y]=mina;
		odlb[x][y]=minb;
		if(tab[x+1][y]&&odla[x+1][y]+odlb[x+1][y]>mina+1+minb) q.push({{x+1, y}, {mina+1, minb}});
		if(tab[x][y+1]&&odla[x][y+1]+odlb[x][y+1]>mina+1+minb) q.push({{x, y+1}, {mina+1, minb}});
		if(tab[x-1][y]&&odla[x-1][y]+odlb[x-1][y]>mina+1+minb) q.push({{x-1, y}, {mina, minb+1}});
		if(tab[x][y-1]&&odla[x][y-1]+odlb[x][y-1]>mina+1+minb) q.push({{x, y-1}, {mina, minb+1}});
	}
}	

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin>>n>>m>>k;
	for(int i=1; i<=n; i++)
	{
		for(int j=1; j<=m; j++)
		{
			char znak;
			cin>>znak;
			odla[i][j]=MAXN*MAXN;
			odlb[i][j]=MAXN*MAXN;
			if(znak=='.') tab[i][j]=1;
		} 
	}
	bfs(1, 1);
	for(int i=0; i<k; i++)
	{
		cin>>a[i]>>b[i];
		mini=min(mini, (long long)(a[i]*odla[n][m]+b[i]*odlb[n][m]));
	}
	for(int i=0; i<k; i++)
	{
		if(a[i]*odla[n][m]+b[i]*odlb[n][m]==mini) ile++;
	}
	cout<<mini<<" "<<ile<<endl;
	return 0;
}