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
// Wycieczka górska [C].cpp : Ten plik zawiera funkcję „main”. W nim rozpoczyna się i kończy wykonywanie programu.
//
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;

long long warstwa[2004][2004];
queue<int>Q_x;
queue<int>Q_y;
vector<int> w;

bool odw[2009][2009];
char tab[2009][2009];
int dx[] = { 0,0,-1,1 };
int dy[] = { 1,-1,0,0 };
int ile_x = 0, ile_y = 0, nX, nY;    // ile_x, ile_y --> rozmiary tablicy

void bfs(int x, int y) {                             // kod na bfs dwuwymiarowego napisany przeze mnie
	Q_x.push(x);
	Q_y.push(y);
	odw[x][y] = 1;
	while (!Q_x.empty() && !Q_y.empty()) {
		x = Q_x.front();
		y = Q_y.front();
		Q_x.pop();
		Q_y.pop();
		for (int i = 0; i < 4; i++) {
			nX = x + dx[i];
			nY = y + dy[i];
			if (nX<1 || nY>ile_y) continue;
			if (nY<1 || nX>ile_x) continue;
			if (tab[nX][nY] == 'X') continue;
			if (odw[nX][nY] == 1) continue;
			odw[nX][nY] = 1;
			Q_x.push(nX);
			Q_y.push(nY);
			warstwa[nX][nY] = warstwa[x][y] + 1;

		}
	}                                               // koniec kodu
}


long long w2[1000009];

int main()
{
    long long n,m, k, bl, po, a,b;
    cin >> ile_x >> ile_y >> k;
    for (int i = 1; i <= ile_x; i++) {
        for (int j = 1; j <= ile_y; j++) {
			cin >> tab[i][j];
        }
    }
	bfs(1, 1);
	n = ile_x;
	m = ile_y;
	bl = (warstwa[n][m] - (n + m - 2)) / 2;
	po = warstwa[n][m] - bl;
	for (int i = 0; i < k; i++) {
		cin >> a >> b;
		w2[i] = a * po + b * bl;
	}
	sort(w2, w2 + k);
	cout << w2[0] << " ";
	long long t = 0, in = 0;
	while (w2[in] == w2[0]) {
		in++;
		t++;
	}
	cout << t;

}