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

bool isInside(std::pair<int, int> p, std::pair<int, int> dim) {
	return p.first >= 0 && p.first < dim.first && p.second >= 0 && p.second < dim.second;
}

std::pair<int, int> findPath(const std::vector<std::string>& grid) {
	//std::vector<std::pair<int, int>> q = {{0, 0}};
	std::queue<std::pair<int,int>> q;
	q.push({0, 0});

	std::pair<int, int> dim = {grid.size(), grid[0].length()};
	auto visited = std::vector<std::vector<bool>>(dim.first, std::vector<bool>(dim.second, false));
	auto steps = std::vector<std::vector<std::pair<int, int>>>(dim.first, std::vector<std::pair<int, int>>(dim.second));
	steps[0][0] = {0, 0};
	visited[0][0] = true;
	while(!q.empty()) {
		auto p = q.front();
		q.pop();
		auto v = steps[p.first][p.second];
		if (p.first == dim.first - 1 && p.second == dim.second - 1) {
			return v;
		}

		if (isInside({p.first + 1, p.second}, dim) && !visited[p.first + 1][p.second] && grid[p.first + 1][p.second] != 'X') {
			steps[p.first + 1][p.second] = {v.first + 1, v.second};
			visited[p.first + 1][p.second] = true;
			q.push({p.first + 1, p.second});
		}
		if (isInside({p.first - 1, p.second}, dim) && !visited[p.first - 1][p.second] && grid[p.first - 1][p.second] != 'X') {
			steps[p.first - 1][p.second] = {v.first, v.second + 1};
			visited[p.first - 1][p.second] = true;
			q.push({p.first - 1, p.second});
		}
		if (isInside({p.first, p.second + 1}, dim)  && !visited[p.first][p.second + 1] && grid[p.first][p.second + 1] != 'X') {
			steps[p.first][p.second + 1] = {v.first + 1, v.second};
			visited[p.first][p.second + 1] = true;
			q.push({p.first, p.second + 1});
		}
		if (isInside({p.first, p.second - 1}, dim)  && !visited[p.first][p.second - 1] && grid[p.first][p.second - 1] != 'X') {
			steps[p.first][p.second - 1] = {v.first, v.second + 1};
			visited[p.first][p.second - 1] = true;
			q.push({p.first, p.second - 1});
		}
	}
}

int main() {
	int n, m, k;
	std::cin >> n >> m >> k;

	std::vector<std::string> grid;
	for (int i = 0; i < n; i++) {
		std::string row;
		std::cin >> row;
		grid.push_back(row);
	}

	auto steps = findPath(grid);

	long long best = 1LL << 60;
	std::vector<std::pair<int, int>> participants;
	for (int i = 0; i < k; i++) {
		int up, down;
		std::cin >> up >> down;
		participants.push_back({up, down});
		best = std::min(best, (long long)steps.first * up + (long long)steps.second * down);
	}

	int count = 0;
	for (auto p: participants) {
		if ((long long)steps.first * p.first + (long long)steps.second * p.second == best) {
			++count;
		}
	}
	std::cout << best << " " << count << '\n';
	return 0;
}