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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include <bits/stdc++.h>
using namespace std;


// QItem for current location and distance
// from source location
class QItem {
public:
    int row;
    int col;
    int dist;
    QItem(int x, int y, int w)
        : row(x), col(y), dist(w)
    {
    }
};

long long minDistance(vector<vector<char> >grid, int N, int M,long long a,long long b)
{
    QItem source(0, 0, 0);

    // To keep track of visited QItems. Marking
    // blocked cells as visited.
    bool visited[N][M];
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++)
        {
            if (grid[i][j] == 'X')
                visited[i][j] = true;
            else
                visited[i][j] = false;

            // Finding source
            if (grid[i][j] == 's')
            {
               source.row = i;
               source.col = j;
            }
        }
    }

    // applying BFS on matrix cells starting from source
    queue<QItem> q;
    q.push(source);
    visited[source.row][source.col] = true;
    while (!q.empty()) {
        QItem p = q.front();
        q.pop();

        // Destination found;
        if (grid[p.row][p.col] == 'd')
            return p.dist;

        // moving up
        if (p.row - 1 >= 0 &&
            visited[p.row - 1][p.col] == false) {
            q.push(QItem(p.row - 1, p.col, p.dist + b));
            visited[p.row - 1][p.col] = true;
        }

        // moving down
        if (p.row + 1 < N &&
            visited[p.row + 1][p.col] == false) {
            q.push(QItem(p.row + 1, p.col, p.dist + a));
            visited[p.row + 1][p.col] = true;
        }

        // moving left
        if (p.col - 1 >= 0 &&
            visited[p.row][p.col - 1] == false) {
            q.push(QItem(p.row, p.col - 1, p.dist + b));
            visited[p.row][p.col - 1] = true;
        }

         // moving right
        if (p.col + 1 < M &&
            visited[p.row][p.col + 1] == false) {
            q.push(QItem(p.row, p.col + 1, p.dist + a));
            visited[p.row][p.col + 1] = true;
        }
    }

    return -1;
}

// Driver code
int main()
{
    int N,M,q;
    cin >> N >> M >> q;
    /*
    vector<vector<char> > grid { { 's', '.', '.', '.','.','.','X' },
                        { 'X', '.', 'X', '.','.','X','.' },
                        {'.', '.', 'X', '.','X','.','X' },
                        { '.', 'X', '.', 'X','.','.','.'},
                        {'.', '.', '.', '.','.','X','d'} };
    */
    vector<vector<char> > grid;
    for(int i=0; i<N; ++i){
        vector<char>v;
        for(int j=0; j<M; ++j){
            char temp;
            cin >> temp;
            v.push_back(temp);
        }
        grid.push_back(v);
    }

    grid[0][0] = 's';
    grid[N-1][M-1]='d';

    vector<long long>results;

    long long final_num;
    for(int i=0; i<q; ++i){
        long long a,b;
        cin >> a >> b;
        final_num = minDistance(grid,N,M,a,b);
        results.push_back(final_num);
    }
    long long licznik = 0;
    auto max_element_of_results = *min_element(results.begin(),results.end());
    for(auto a : results){
        if(a==max_element_of_results){
            licznik++;
        }
    }
    cout << final_num << " " << licznik;
    /*
    char grid[N][M] = { { 's', 'X', '.', '.','.'},
                        { '.', '.', '.', 'X','d'}};
    */


    return 0;
}

/*UWAGA WAZNA ZMIANA PRZY DYSTANSIE*/