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
#include<bits/stdc++.h>                                                         
using namespace std;                                                            
                                                                                
int n,m,k;                                                                      

char s;                                                                         
pair <int, int> x;                                                              

int main(){                                                                     
    ios_base::sync_with_stdio(0);                                               
    cin.tie(0);                                                                 
                                                                                
    cin>>n>>m>>k;                                                               
    vector<vector<int> > V (n+2);                                               

    for(int i=0; i<=n+1; i++) V[i].resize(m+2);                                 

                                                                                
    for(int i=0; i<=n+1; i++){                                                  

        V[i][0]=-1;                                                             
        V[i][m+1]=-1;                                                           
    }                                                                           
    for(int i=0; i<=m+1; i++){                                                  

        V[0][i]=-1;                                                             
        V[n+1][i]=-1;                                                           
    }                                                                           
                                                                                
    for(int i=1; i<=n; i++){                                                    

        for(int j=1; j<=m; j++){                                                

            cin>>s;                                                             

            if(s=='X') V[i][j]=-1;                                              
        }                                                                       
    }                                                                           
                                                                                
    stack<  pair <int, int> > Q;                                                

    Q.push(make_pair(1,1));                                                     
    V[1][1]=1;                                                                  
    while(!Q.empty()){                                                          
        x=Q.top();                                                              

        Q.pop();                                                                
                                                                                
        if(V[x.first+1][x.second]!=-1){                                         
            if(V[x.first+1][x.second]==0){                                      
                V[x.first+1][x.second]= V[x.first][x.second]+1;                 
                Q.push(make_pair(x.first+1,x.second));                          
            }else{                                                              
                if(V[x.first+1][x.second]>V[x.first][x.second]+1){              
                    V[x.first+1][x.second]=V[x.first][x.second]+1;              
                    Q.push(make_pair(x.first+1,x.second));                      
                }                                                               
            }                                                                   

        }                                                                       
                                                                                
        if(V[x.first][x.second+1]!=-1){                                         
            if(V[x.first][x.second+1]==0){                                      
                V[x.first][x.second+1]= V[x.first][x.second]+1;                 
                Q.push(make_pair(x.first,x.second+1));                          
            }else{                                                              
                if(V[x.first][x.second+1]>V[x.first][x.second]+1){              
                    V[x.first][x.second+1]=V[x.first][x.second]+1;              
                    Q.push(make_pair(x.first,x.second+1));                      
                }                                                               
            }                                                                   
        }                                                                       
                                                                                
        if(V[x.first-1][x.second]!=-1){                                         
            if(V[x.first-1][x.second]==0){                                      
                V[x.first-1][x.second]= V[x.first][x.second];                   
                Q.push(make_pair(x.first-1,x.second));                          
            }else{                                                              
                if(V[x.first-1][x.second]>V[x.first][x.second]){                
                    V[x.first-1][x.second]=V[x.first][x.second];                
                    Q.push(make_pair(x.first-1,x.second));                      
                }                                                               
            }                                                                   
        }                                                                       
                                                                                
        if(V[x.first][x.second-1]!=-1){                                         
            if(V[x.first][x.second-1]==0){                                      
                V[x.first][x.second-1]= V[x.first][x.second];                   
                Q.push(make_pair(x.first,x.second-1));                          
            }else{                                                              
                if(V[x.first][x.second-1]>V[x.first][x.second]){                
                    V[x.first][x.second-1]=V[x.first][x.second];                
                    Q.push(make_pair(x.first,x.second-1));                      
                }                                                               
            }                                                                   
        }                                                                       
    }                                                                           
    long long wyn,sum;                                                          
    long long d=n+m-2;                                                          

    sum= (long long)V[n][m];                                                    
    sum=sum-d-1;                                                                
    int ile=1;                                                                  
    long long a,b,ww;                                                           
    cin>>a>>b;                                                                  

    wyn=d*a+(a+b)*sum;                                                          
    for(int i=1; i<k; i++){                                                     
        cin>>a>>b;                                                              

        ww=d*a+(a+b)*sum;                                                       
        if(wyn==ww) ile++;                                                      
        if(wyn>ww){                                                             
            wyn=ww;                                                             
            ile=1;                                                              
        }                                                                       
    }                                                                           
    cout<<wyn<<" "<<ile;                                                        
    return 0;                                                                   
                                                                                
}