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
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <deque>
#include <tuple>
#include <map>
using namespace std;

int n = 0;
int m = 0;
deque<tuple<char,int,int>> mapa;

int kick_it (int x, int y) {

    int koszt1 = get<1>(mapa.at(x+(y)*m));
    int koszt2 = get<2>(mapa.at(x+(y)*m));
    int offset = x+y*m;
    //cout << "kick it! " << x << ' ' << y << ' ' << koszt1 << ' ' << koszt2 << "\n";
    
    if (y < n -1) {
        if (get<0>(mapa.at(offset + m)) == '.') {
            if (get<2>(mapa.at(offset + m)) > koszt2+1) {
                mapa[offset + m] = make_tuple('.', koszt1+1, koszt2);
                kick_it(x,y+1);
            }
        }
    }
    if (y > 0) {
        if (get<0>(mapa.at(offset - m)) == '.') {
            if (get<2>(mapa.at(offset - m)) > koszt2+1) {
                mapa[offset - m] = make_tuple('.', koszt1, koszt2+1);
                kick_it(x,y-1);
            }
        }
    }
    if (x < m - 1) {
        if (get<0>(mapa.at(offset + 1)) == '.') {
            if (get<2>(mapa.at(offset + 1)) > koszt2+1) {
                mapa[offset + 1] = make_tuple('.', koszt1+1, koszt2);
                kick_it(x+1,y);
            }
        }
    }
    if (x > 0) {
        if (get<0>(mapa.at(offset - 1)) == '.') {
            if (get<2>(mapa.at(offset - 1)) > koszt2+1) {
                mapa[offset - 1] = make_tuple('.', koszt1, koszt2+1);
                kick_it(x-1,y);
            }
        }
    }
    return 0;
}


main (int arc, char ** argv) {

    int k = 0;
    cin >> n >> m >> k;
    //cout << n << '\n';

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            char pole;
            cin >> pole;

            if (pole == '.') {
                mapa.push_back(make_tuple(pole,4000000,4000000));
                //cout << "pole: " << pole <<'\n';
            } else {
                mapa.push_back(make_tuple(pole,-4000000,-4000000));
                //cout << "pole: " << pole <<'\n';
            }

            //cout << "get<0>(mapa.at(j+i*n)" << get<0>(mapa.at(j+i*n)) << '\n';
        }
    }

    mapa.at(0) = make_tuple('.',0,0);
    kick_it (0, 0);
    //cout << "result:" << result <<'\n';

    int koszt1 = get<1>(mapa.at(n*m-1));
    int koszt2 = get<2>(mapa.at(n*m-1));

    std::map<int, int> czasy;
    std::map<int,int>::iterator it;

    for (int i = 0; i < k; i++) {
        int a = 0;
        int b = 0;
        cin >> a >> b;

        it = czasy.find(a*koszt1+b*koszt2);
       
        if (it == czasy.end()) {
            czasy.insert(make_pair(a*koszt1+b*koszt2,1));
        } else {
            it->second++;
        }

        //do multiseta
    }
    //cout << "result:" << get<1>(mapa.at(n*m-1)) <<'\n';
    //cout << "result:" << a*koszt1+b*koszt2 <<'\n';

    it = czasy.begin();
    cout << it->first << ' ' << it->second << '\n';

    return 0;
}