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
#include <bits/stdc++.h>
using namespace std;
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	long long n, m, k, a, b;
	char x;
	cin>>n>>m>>k;
	long long tab[n+2][m+2] = {0};
	for(long long i=1; i<=n; i++){
		for(long long j=1; j<=m; j++){
			cin>>x;
			if(x=='X'){
				tab[i][j]=-1;
			}
		}
	}
	for(long long i = 0; i<=m+1; i++){
		tab[0][i]=-1;
		tab[n+1][i]=-1;
	}
	for(long long i = 0; i<=n+1; i++){
		tab[i][0]=-1;
		tab[i][m+1]=-1;
	}
	queue <long long> pierw;
	queue <long long> dru;
	pierw.push(1);
	dru.push(1);
	tab[1][1]=1;
	while(!pierw.empty()&&tab[n][m]==0){
		if(tab[pierw.front()+1][dru.front()]==0){
			tab[pierw.front()+1][dru.front()]=tab[pierw.front()][dru.front()]+1;
			pierw.push(pierw.front()+1);
			dru.push(dru.front());
		}
		if(tab[pierw.front()][dru.front()+1]==0){
			tab[pierw.front()][dru.front()+1]=tab[pierw.front()][dru.front()]+1;
			pierw.push(pierw.front());
			dru.push(dru.front()+1);
		}
		if(tab[pierw.front()-1][dru.front()]==0){
			tab[pierw.front()-1][dru.front()]=tab[pierw.front()][dru.front()]+1;
			pierw.push(pierw.front()-1);
			dru.push(dru.front());
		}
		if(tab[pierw.front()][dru.front()-1]==0){
			tab[pierw.front()][dru.front()-1]=tab[pierw.front()][dru.front()]+1;
			pierw.push(pierw.front());
			dru.push(dru.front()-1);
		}
		pierw.pop();
		dru.pop();
	}
	cin>>a>>b;
	long long d = (tab[n][m]-n-m+1)/2;
	long long c = n+m-2+d;
	long long suma = c*a+d*b;
	long long wynik = 1;
	for(long long i=1; i<k; i++){
		cin>>a>>b;
		if(c*a+d*b==suma){
			wynik++;
		}
		if(c*a+d*b<suma){
			suma = c*a+d*b;
			wynik=1;
		}
	}
	cout<<suma<<" "<<wynik;
}