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
#include <stdio.h>
#include <queue>
#include <tuple>
#include <set>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>

using namespace std;

int main(){
    long long int n, m, k;
    scanf("%lld %lld %lld\n", &n, &m, &k);

    vector<vector<int>> map;
    vector<vector<pair<int, int>>> results;
    set<pair<int, int>> visited;

    for (int idx=0; idx<n; ++idx) {
        map.push_back(vector<int>(m, 0));
        results.push_back(vector<pair<int,int>>(m, make_pair(0,0)));
    }

    string inStr;
    for (int idx=0; idx<n; ++idx) {
        cin >> inStr;
        for (int inIdx=0; inIdx<m; ++inIdx) {
            if (inStr[inIdx] == 'X') {
                map[idx][inIdx] = 1;
            }
        }
    }

    int ROWS [4] = {1, 0, -1, 0};
    int COLS [4] = {0, 1, 0, -1};
    priority_queue<tuple<int, int, int, int>> que;
    tuple<int, int, int, int> el;
    que.push(make_tuple(0,0,0,0));
    visited.insert(make_pair(0,0));
    while (!que.empty()) {
        el = que.top();
        int x = get<2>(el);
        int y = get<3>(el);
        int a = get<0>(el);
        int b = get<1>(el);

//        cout << a << " "<< b << " "<< x << " "<< y << " "<< que.size() << "\n";
        que.pop();
//        if (que.size() > 0) {
//            el = que.top();
//            int x1 = get<2>(el);
//            int y1 = get<3>(el);
//            int a1 = get<0>(el);
//            int b1 = get<1>(el);
//            cout << a1 << " "<< b1 << " "<< x1 << " "<< y1 << " "<< que.size() << "\n\n\n";
//        }

        for (int idx=0; idx < 4; ++idx) {
            int newX = x + ROWS[idx];
            int newY = y + COLS[idx];
            if (newX < 0 || newY < 0 || newX >= n ||  newY >= m) {
                continue;
            }
            if (visited.find(make_pair(newX, newY)) != visited.end()) {
                continue;
            }
            visited.insert(make_pair(newX, newY));
            if (map[newX][newY] == 1) {
                continue;
            }
            if (idx < 2) {
                que.push(make_tuple(a - 1, b, newX, newY));
            } else {
                que.push(make_tuple(a, b - 1, newX, newY));
            }
        }

        results[x][y] = make_pair(a, b);

    }

//    for (int row =0; row < n; ++row) {
//        for (int col=0; col<m; ++col) {
//            cout << results[row][col].first << " ";
//        }
//        cout << "\n";
//    }

    pair<int, int> xd = results[n-1][m-1];
    long long int counter = 0, lowest =  2147483646;
    long long int aV, bV;
    long long dd;
    for (int idx = 0; idx < k; ++idx) {
        scanf("%lld %lld\n", &aV, &bV);
        dd = -1*aV*xd.first + -1*bV*xd.second;
        if (lowest == dd) {
            counter ++;
        } else {
            if (lowest > dd) {
                counter = 1;
                lowest = dd;
            }
        }
    }

    printf("%lld %lld\n", lowest, counter);


    return 0;
}