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
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
// wyc-wycieczka-gorska.cpp : Ten plik zawiera funkcję „main”. W nim rozpoczyna się i kończy wykonywanie programu.
//

#include <iostream>
#include <stack>
#include <utility>
#include <algorithm>

constexpr int MAXN = 2007;
constexpr int INF = 100000000;
constexpr int MAXK = 1000007;
constexpr int MAXNM = MAXN * MAXN;
constexpr long long INFL = 1000000000000000000;

bool t[MAXN][MAXN];
//int dp[MAXN][MAXN];
int vst[MAXN][MAXN];
bool vstd[MAXN][MAXN];
std::stack< std::pair<int, int> > st[2];
long long av[MAXK];
long long bv[MAXK];

inline void putval(int x, int y, int v, int v2)
{
	if (t[x][y] && vst[x][y]>v2)
	{
		st[v].push(std::make_pair(x, y));
		vst[x][y] = v2;
	}
}

int main()
{
	std::ios_base::sync_with_stdio(0);
	std::cin.tie(0);
	std::cout.tie(0);
	int n, m, k, x, y, hmi, q;
	long long mnval, hmv, lmn;
	std::string s;
	std::cin >> n >> m >> k;
	for (size_t i = 1; i <= n; i++)
	{
		std::cin >> s;
		for (size_t j = 0; j < m; j++)
		{
			t[i][j+1] = s[j] == '.';
		}
	}
	for (size_t i = 0; i < MAXN; i++)
	{
		for (size_t j = 0; j < MAXN; j++)
		{
			vst[i][j] = INF;
		}
	}
	vst[1][1] = 0;
	vstd[0][0] = 1;
	st[0].push(std::make_pair(1,1));
	for (size_t i = 0; i < m*n+3; i++)
	{
		q = i % 2;
		while (!st[q].empty())
		{
			auto v = st[q].top();
			st[q].pop();
			if (vstd[v.first][v.second])
			{
				continue;
			}
			x = v.first;
			y = v.second;
			if (x==n && y==m)
			{
				hmv = i;
			}
			//dp[x][y] = i;
			vstd[x][y] = 1;
			putval(x + 1, y, q, i);
			putval(x, y + 1, q, i);
			putval(x - 1, y, !q, i+1);
			putval(x, y - 1, !q, i+1);
		}
	}
	lmn = m + n - 2;
	mnval = INFL;
	for (size_t i = 1; i <= k; i++)
	{
		std::cin >> av[i] >> bv[i];
		mnval = std::min((av[i] + bv[i])* hmv + av[i] * lmn, mnval);
	}
	std::cout << mnval << ' ';
	hmi = 0;
	for (size_t i = 1; i <= k; i++)
	{
		if ((av[i] + bv[i]) * hmv + av[i] * lmn == mnval)
		{
			hmi++;
		}
	}
	std::cout << hmi << '\n';
}

// Uruchomienie programu: Ctrl + F5 lub menu Debugowanie > Uruchom bez debugowania
// Debugowanie programu: F5 lub menu Debugowanie > Rozpocznij debugowanie

// Porady dotyczące rozpoczynania pracy:
//   1. Użyj okna Eksploratora rozwiązań, aby dodać pliki i zarządzać nimi
//   2. Użyj okna programu Team Explorer, aby nawiązać połączenie z kontrolą źródła
//   3. Użyj okna Dane wyjściowe, aby sprawdzić dane wyjściowe kompilacji i inne komunikaty
//   4. Użyj okna Lista błędów, aby zobaczyć błędy
//   5. Wybierz pozycję Projekt > Dodaj nowy element, aby utworzyć nowe pliki kodu, lub wybierz pozycję Projekt > Dodaj istniejący element, aby dodać istniejące pliku kodu do projektu
//   6. Aby w przyszłości ponownie otworzyć ten projekt, przejdź do pozycji Plik > Otwórz > Projekt i wybierz plik sln