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
115
116
117
118
119
120
121
122
#include <iostream>
#include <queue>

using namespace std;

int n,m,k;
long long sumA,sumB;

bool mapa[2020][2020];
bool vis[2020][2020];

struct Point
{
    int x;
    int y;
};

struct queueNode
{
    Point pt;
    long long a,b;
};

bool ok(int row, int col)
{
    return (row > 0) && (row <= n) &&(col > 0) && (col <= m);
}

int rowNum[] = {-1, 0, 0, 1};
int colNum[] = {0, -1, 1, 0};

void BFS(Point src, Point dest)
{
    vis[src.x][src.y] = true;

    queue<queueNode> q;

    queueNode s = {src, 0,0};
    q.push(s);

    while (!q.empty())
    {
        queueNode curr = q.front();
        Point pt = curr.pt;

        if (pt.x == dest.x && pt.y == dest.y)
        {
            sumA=curr.a;
            sumB=curr.b;
            return;
        }

        q.pop();

        for (int i = 0; i < 4; i++)
        {
            int row = pt.x + rowNum[i];
            int col = pt.y + colNum[i];

            if (ok(row, col) && mapa[row][col] && !vis[row][col])
            {
                vis[row][col] = true;

                queueNode Adjcell;
                if(rowNum[i]>=0 && colNum[i]>=0)
                    Adjcell = {{row, col}, curr.a+1, curr.b};
                else
                    Adjcell = {{row, col}, curr.a, curr.b+1};

                q.push(Adjcell);
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    char ch;
    cin>>n>>m>>k;

    for(int i=1; i<=n; ++i)
    {
        for(int j=1; j<=m; ++j)
        {
            cin>>ch;
            if(ch == '.')
                mapa[i][j]=true;
        }
    }

    Point source = {1, 1};
    Point dest = {n, m};
    BFS(source, dest);

    int a,b;
    long long odp1, odpT;
    int odp2=1;

    cin>>a>>b;
    odp1 = a*sumA+b*sumB;

    for(int i=1; i<k; ++i)
    {
        cin>>a>>b;
        odpT = a*sumA+b*sumB;

        if(odpT < odp1)
        {
            odp1 = odpT;
            odp2=1;
        }
        else if(odpT == odp1)
            odp2++;
    }

    cout<<odp1<<' '<<odp2;

    return 0;
}