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
#include <iostream>
#include <vector>
#include <queue>
#include <utility>

void process(const std::vector<std::vector<char>>& graph, std::vector<std::vector<long long>>& visited, long long x, long long y, long long current, std::queue<std::pair<long long, long long>>& q)
{
	if (graph[x][y] == 'X')
		return;
	if (visited[x][y] != -1)
		return;
	visited[x][y] = current;
	q.push({ x,y });
}

void bfs(const std::vector<std::vector<char>>& graph, std::vector<std::vector<long long>>& visited)
{
	visited[1][1] = 0;
	std::queue<std::pair<long long, long long>> q;
	q.push({ 1, 1 });
	while (!q.empty())
	{
		std::pair<long long, long long> p;
		p = q.front();
		q.pop();
		process(graph, visited, p.first + 1, p.second, visited[p.first][p.second] + 1, q);
		process(graph, visited, p.first - 1, p.second, visited[p.first][p.second] + 1, q);
		process(graph, visited, p.first, p.second + 1, visited[p.first][p.second] + 1, q);
		process(graph, visited, p.first, p.second - 1, visited[p.first][p.second] + 1, q);
	}
}

int main()
{
	std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0);
	long long n, m, k;
	std::cin >> n >> m >> k;
	n += 2;
	m += 2;
	std::vector<std::vector<char>> labirynth(n);
	std::vector<std::vector<long long>> visited(n);
	for (long long i = 0; i < n; ++i)
	{
		labirynth[i].resize(m);
		visited[i].resize(m);
		for (long long j = 0; j < m; ++j)
		{
			visited[i][j] = -1;
			if (i == 0 || j == 0 || i == n - 1 || j == m - 1)
				labirynth[i][j] = 'X';
			else
				std::cin >> labirynth[i][j];
		}
	}
	bfs(labirynth, visited);
	long long min = 0;
	long long counter = 0;
	for (long long i = 0; i < k; ++i)
	{
		long long a, b;
		std::cin >> a >> b;
		long long t = (n + m - 6) * a + (visited[n - 2][m - 2] - n - m + 6) * (a + b) / 2;
		if (i == 0)
		{
			min = t;
			counter = 1;
		}
		else
		{
			if (t == min)
				++counter;
			if (t < min)
			{
				min = t;
				counter = 1;
			}
		}
	}
	std::cout << min << " " << counter << std::endl;
}