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 max wierzcholki
#define ll long long

vector <vector <ll> > graf;
int wierzcholki;
ll wgore = 0, wdol = 0;
vector <int> P;
vector <bool> odwiedzony;



void bfs(int odkad, int dokad)
{
	queue <ll> Q;
	vector <ll> odleg(max, 0);
	vector <bool> czyodw(max, false);
	Q.push(odkad);
	czyodw[odkad] = true;
	while(!Q.empty()) {
		ll w = Q.front();
		Q.pop();
		for (int i = 0; i < graf[w].size(); i++) {
			int sasiad = graf[w][i];
			if (czyodw[sasiad] == false) {
				//cout << "\n" << sasiad << " " << w << "\n";
				P[sasiad] = w;
				odleg[sasiad] = odleg[w] + 1;
				czyodw[sasiad] = true;
				Q.push(sasiad);
			}
		}
	}
}


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int wiersze, kolumny, znajomi;
	cin >> wiersze >> kolumny >> znajomi;
	wierzcholki = wiersze * kolumny;
	graf.resize(wierzcholki);
	P.resize(wierzcholki);
	odwiedzony.resize(max);
	vector <string> mapa(wiersze);
	for (int i = 0; i < wiersze; i++) {
		string a;
		cin >> a;
		mapa[i] = a;
	}
	for (int i = 0; i < wiersze; i++) {
		for (int j = 0; j < kolumny; j++) {
			if (mapa[i][j] == '.') {
				if (i > 0 && mapa[i - 1][j] == '.')
					graf[i * kolumny + j].emplace_back((i - 1) * kolumny + j);
				if (i < wiersze - 1 && mapa[i + 1][j] == '.')
					graf[i * kolumny + j].emplace_back((i + 1) * kolumny + j);
				if (j > 0 && mapa[i][j - 1] == '.')
					graf[i * kolumny + j].emplace_back(i * kolumny + j - 1);
				if (j < kolumny - 1 && mapa[i][j + 1] == '.')
					graf[i * kolumny + j].emplace_back(i * kolumny + j + 1);
			}
		}
	}
	ll wynik = LLONG_MAX;
	ll ile = 0;
	bfs(0, wierzcholki - 1);
	int iter = wierzcholki - 1;
	while (iter > 0){
		//cout << P[iter] << " " << iter << "\n";
		if (P[iter] > iter) wdol++;
		else wgore++;
		iter = P[iter];
	}
	//cout << wgore << " " << wdol;
	for (int i = 0; i < znajomi; i++) {
		ll twgore, twdol;
		cin >> twgore >> twdol;	
		ll temp = twgore * wgore + twdol * wdol;
		if (wynik > temp) {
			wynik = temp;
			ile = 1;
		}
		else if (wynik == temp)
			ile++;
	}
	cout << wynik << " " << ile;
	return 0;
}