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
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#define INT_MAX 2000000000

const int SIZE = 2001;
const int SIZE2 = SIZE * SIZE;
std::vector<int> graph[SIZE];
int rows, columns, k;
bool visited[SIZE2];
int prev[SIZE2];
int dist[SIZE2];

void addAdjacents(int id, int row, int column) {
    if(column > 1)          graph[id].push_back(id - 1);
    if(column < columns)    graph[id].push_back(id + 1);
    if(row > 1)             graph[id].push_back(id - columns);
    if(row < rows)          graph[id].push_back(id + columns);
}

void BFS(int src = 1, int dest = rows * columns) {
    std::queue<int> queue;
    for (int i = 0; i <= rows * columns; i++) {
        visited[i] = false;
        dist[i] = INT_MAX;
        prev[i] = -1;
    }
 
    visited[src] = true;
    dist[src] = 0;
    queue.push(src);

    while (!queue.empty()) {
        int u = queue.front();
        queue.pop();
        for (int i = 0; i < graph[u].size(); i++) {
            if (visited[graph[u][i]] == false) {
                visited[graph[u][i]] = true;
                dist[graph[u][i]] = dist[u] + 1;
                prev[graph[u][i]] = u;
                queue.push(graph[u][i]);
 
                if (graph[u][i] == dest)
                    return;
            }
        } 
    }
    return;
}


int main() {
    char ch;
    int it = 0;
    int a, b, time, minTime = INT_MAX, out = 0, higher = 0, lower = 0;
    std::vector<int> times;
    scanf("%d%d%d", &rows, &columns, &k);
    
    for(int i = 1; i <= rows; i++) {
        for(int j = 1; j <= columns; j++) {
            it++;
            scanf(" %c", &ch);
            if(ch == '.')
                addAdjacents(it, i, j);
        }
    }
    BFS();
    int temp = prev[rows * columns];
    while(temp != -1) {
            if(prev[temp] < temp)
                higher++;
            else lower++;
            temp = prev[temp];
    }

    for(int i = 0; i < k; i++) {
        scanf("%d%d", &a, &b);
        time = higher * a + lower * b;
        minTime = std::min(minTime, time);
        times.push_back(time);
    }
    for(auto q : times)
        if(q == minTime)
            out++;

    printf("%d %d", minTime, out);
}