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
#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <limits>
using namespace std;

int DirX[4]      = { 0, 1, 0, -1};
int DirY[4]      = {-1, 0, 1,  0};
int DeltaDist[4] = { 1, 0, 0,  1};

struct Point{
    int x,y;
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    vector<string>Map(n);
    for(string &row : Map)
        cin >> row;
    
    vector<vector<int>>DownhillDist(n, vector<int>(m, 1000000000));
    vector<vector<bool>>Processed(n, vector<bool>(m, false));

    queue<Point>CurrentQ, NextQ;
    CurrentQ.push(Point{0,0});
    DownhillDist[0][0]=0;

    while(!CurrentQ.empty()){
        while(!CurrentQ.empty()){
            Point p = CurrentQ.front();
            CurrentQ.pop();
            if(Processed[p.y][p.x])
                continue;
            Processed[p.y][p.x]=true;

            for(int dir=0;dir<4;dir++){
                int x = p.x+DirX[dir];
                int y = p.y+DirY[dir];
                int dist = DownhillDist[p.y][p.x]+DeltaDist[dir];
                if(x>=0 && x<m && y>=0 && y<n && Map[y][x]=='.' && DownhillDist[y][x]>dist){
                    DownhillDist[y][x] = dist;
                    if(DeltaDist[dir])
                        NextQ.push(Point{x,y});
                    else
                        CurrentQ.push(Point{x,y});
                }
            }
        }

        CurrentQ.swap(NextQ);
    }

    // for(auto row : DownhillDist){
    //     for(auto cell : row)
    //         if(cell==1000000000)
    //             cout << 'X';
    //         else
    //             cout << cell;
    //     cout << endl;
    // }

    long long bestTime=numeric_limits<long long>::max();
    int bestGuys=0;
    while(k--){
        long long a, b;
        cin >> a >> b;

        long long res = (n+m-2)*a + DownhillDist.back().back()*(a+b);
        if(bestTime>res){
            bestTime=res;
            bestGuys=1;
        }
        else if(bestTime==res)
            bestGuys++;
    }

    cout << bestTime << " " << bestGuys << "\n";

    return 0;
}