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
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a); i<(b); ++i)
typedef vector<int> vi;
#define pb push_back
#define sz size()
typedef pair<int,int> pii;
#define mp make_pair
#define st first
#define nd second
typedef long long ll;
#define INF 1000000001
#define ALL(t) t.begin(),t.end()
#define SC(a) scanf("%d", &a)
#define GET(a) int a; SC(a)

#define ISDEBUG 0
#define dprintf(...) if(ISDEBUG) \
{printf("\033[31m"); printf(__VA_ARGS__); printf("\033[0m");}
template <class It> void dptab(It b, It e, const char* f="%d ") {
	if(ISDEBUG) {
		for(It it=b; it!=e; ++it) dprintf(f, *it); dprintf("\n");
}}

int g[2002][2002];

vector<pii> next_start;


void visit(int i, int j, int step) {
	if(g[i][j] != INF) return;
	g[i][j] = step;
	dprintf("visiting (%d, %d)   step #%d\n", i, j, step);
	if (g[i+1][j] == INF) visit(i+1, j, step);
	if (g[i][j+1] == INF) visit(i, j+1, step);
	if (g[i-1][j] == INF) {
		dprintf("adding (%d, %d) to visit next\n", i-1, j);
		next_start.pb({i-1, j});
	}
	if (g[i][j-1] == INF) {
		dprintf("adding (%d, %d) to visit next\n", i, j-1);
		next_start.pb({i, j-1});
	}
}

int main() {
	GET(n);
	GET(m);
	GET(k);
	FOR(i,0,n+2) {
		g[i][0] = -1;
		g[i][m+1] = -1;
	}
	FOR(i,0,m+2) {
		g[0][i] = -1;
		g[n+1][i] = -1;
	}
	FOR(i,0,n) {
		char buf[2001];
		scanf("%s", buf);
		FOR(j,0,m) {
			if(buf[j] == 'X') {
				g[i+1][j+1] = -1;
			} else if(buf[j] == '.') {
				g[i+1][j+1] = INF;
			}
		}
	}

	next_start.pb({1,1});
	int step = 0;
	while(next_start.sz && g[n][m] == INF) {
		vector<pii> to_visit = next_start;
		next_start = vector<pii>();
		FOR(i,0,to_visit.sz) {
			visit(to_visit[i].first, to_visit[i].second, step);
		}
		step++;
		FOR(i,0,n+2) {
			dptab(g[i], g[i]+(m+2), "%2d ");
		}

	}

	ll min_time = 104004000000000000LL;
	int min_time_counter = 0;
	FOR(i,0,k) {
		GET(a);
		GET(b);
		ll time = (n+m-2)*(ll)a + (ll)g[n][m]*(a+b);
		if(time < min_time) {
			min_time = time;
			min_time_counter = 1;
		} else if(time == min_time) {
			++min_time_counter;
		}

	}
	dprintf("min steps: %d\n", g[n][m]);
	printf("%lld %d\n", min_time, min_time_counter);
	return 0;
}