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
#include<bits/stdc++.h>
using namespace std;
struct pos{
	int x,y,c;
};
bool visited[2000+5][2000+5];
char s[2000+5];
queue <pos> q;
int main(){
	int n,m,k,i,j,a,b,t,answer;
	long long result,pom;
	pos p;
	scanf("%d%d%d",&n,&m,&k);
	for(i=0;i<n;i++){
		scanf("%s",s);
		for(j=0;j<m;j++)
			visited[j][i]=(s[j]=='X');
	}
	q.push({0,0,0});
	while(!q.empty()){
		p=q.front();
		q.pop();
		if(visited[p.x][p.y])
			continue;
		visited[p.x][p.y]=true;
		if(p.x==m-1 && p.y==n-1){
			t=p.c;
			break;
		}
		if(p.x<m-1)
			if(!visited[p.x+1][p.y])
				q.push({p.x+1,p.y,p.c+1});
		if(p.y<n-1)
			if(!visited[p.x][p.y+1])
				q.push({p.x,p.y+1,p.c+1});
		if(p.x>0)
			if(!visited[p.x-1][p.y])
				q.push({p.x-1,p.y,p.c+1});
		if(p.y>0)
			if(!visited[p.x][p.y-1])
				q.push({p.x,p.y-1,p.c+1});
	}
	answer=0;
	result=1000000000000000000+69;
	for(i=0;i<k;i++){
		scanf("%d%d",&a,&b);
		pom=(long long)(m-1+n-1+(t-m+1-n+1)/2)*a+(long long)(t-m+1-n+1)/2*b;
		if(result==pom)
			answer++;
		if(result>pom){
			result=pom;
			answer=1;
		}
	}
	printf("%lld %d\n",result,answer);
}