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
113
114
#include <bits/stdc++.h>
typedef long long ll;

using namespace std;

bool graph[2005][2005];
int n, m, t;
int res;
ll top, bot;
char c;
ll minval = LLONG_MAX, climb;
int counter;

struct vertex
{
    int x1, x2;
    int value;
};

vertex v;
queue<vertex> q;

void bfs(vertex x)
{
    graph[x.x1][x.x2] = 1;
    if(graph[x.x1-1][x.x2] == 0)
    {
        graph[x.x1-1][x.x2] = 1;
        vertex temp = x;
        temp.value++;
        temp.x1--;
        q.push(temp);
    }
    if(graph[x.x1+1][x.x2] == 0)
    {
        graph[x.x1+1][x.x2] = 1;
        vertex temp = x;
        temp.value++;
        temp.x1++;
        q.push(temp);
    }
    if(graph[x.x1][x.x2-1] == 0)
    {
        graph[x.x1][x.x2-1] = 1;
        vertex temp = x;
        temp.value++;
        temp.x2--;
        q.push(temp);
    }
    if(graph[x.x1][x.x2+1] == 0)
    {
        graph[x.x1][x.x2+1] = 1;
        vertex temp = x;
        temp.value++;
        temp.x2++;
        q.push(temp);
    }
    return;
}

int main()
{
    scanf("%d%d%d", &n, &m, &t);
    for(int i = 0; i<=n+1; i++)
    {
        for(int j = 0; j<=m+1; j++)
        {
            graph[0][j] = 1;
            graph[i][0] = 1;
            graph[n+1][j] = 1;
            graph[i][m+1] = 1;
        }
    }
    for(int i = 1; i<=n; i++)
    {
        for(int j = 1; j<=m; j++)
        {
            scanf(" %c", &c);
            if(c == 'X')
            {
                graph[i][j] = 1;
            }
        }
    }
    v.x1 = 1;
    v.x2 = 1;
    v.value = 0;
    q.push(v);
    while(!q.empty()){
        v = q.front();
        q.pop();
        bfs(v);
        if(v.x1 == n && v.x2 == m)
        {
            res = v.value;
        }
    }
    climb = (res - n - m + 2)/2 + m + n - 2;
    for(int i = 1; i<=t; i++)
    {
        scanf("%lld%lld", &top, &bot);
        if(climb * top + (res-climb) * bot == minval)
        {
            counter++;
        }
        if(climb * top + (res-climb) * bot < minval)
        {
            counter = 1;
            minval = climb * top + (res-climb) * bot;
        }
        
    }
    printf("%lld %d", minval, counter);
}