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
#include <bits/stdc++.h> 

using namespace std;

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

    int n,m,k;
    cin>>n>>m>>k;

  
    string tab="";
    string use="";
    vector<int> *sl = new vector<int>[n*m];
    bool *visited = new bool[n*m]; 
    

    //vector<int> v[1000];
    for(int i=0; i<n;i++)
    {
        cin>>use;
        tab+=use;
    }
    for(int i=0;i<n*m;i++)
    {   
        visited[i]=false;
        if(tab[i]!='.')
            continue;
        if(i-m>=0)
            sl[i].push_back(i-m);
        if(i+m<n*m)
            sl[i].push_back(i+m);
        if(i%m!=0)
            sl[i].push_back(i-1);
        if((i+1)%m!=0)
            sl[i].push_back(i+1);
        
    }
    queue<int> Q;
    int *P = new int[n*m];
    Q.push(0);
    int u,v;
    P[0]=-1;
    visited[0]=true;
    while(Q.empty()==false)
    {
        v = Q.front();
        Q.pop();
        if(v==n*m-1)
            break;
        for(int i=0;i<sl[v].size();i++)
        {
            u=sl[v].at(i);
            if(!visited[u])
            {
                P[u]=v;
                Q.push(u);
                visited[u]=true;
            }
        }

    }
    int up=0,down=0;
    while(Q.empty()==0)
    {
        Q.pop();
    }
    while(v>0)
    {
        if(P[v]==v-1 || P[v]==v-m) 
        {
            up++;
        }
        else down++;
        v=P[v];
    }
    int a,b,eq;
    int ans=INT_MAX, count=0;
    for(int i=0;i<k;i++)
    {
        cin>>a>>b;
        eq=a*up+b*down;
        if(eq<ans)
        {
            count=1;
            ans=eq;
        }
        else if(eq==ans)
        {
            count++;
        }
    }
    cout<<ans<<" "<<count;
    delete[] visited;
    delete[] sl;
    delete[] P;
    return 0;
}