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
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

// modified grid BFS from https://www.geeksforgeeks.org/shortest-distance-two-cells-matrix-grid/ (too lazy xD)

// 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)
    {
    }
};

int minDistance(vector<vector<char>> grid, int n, int m)
{
    QItem source(0, 0, 0);

    // To keep track of visited QItems. Marking 
    // blocked cells as visited. 
    vector<vector<bool>> visited(n, vector<bool>(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 + 1));
            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 + 1));
            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 + 1));
            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 + 1));
            visited[p.row][p.col + 1] = true;
        }
    }

    return -1;
}

int main()
{
    ios::sync_with_stdio(false);
    int n, m, k;

    cin >> n >> m >> k;
    
    vector<vector<char>> grid(n, vector<char>(m));

    string row;

    for (int i = 0; i < n; i ++)
    {
        cin >> row;
        
        for (int j = 0; j < row.length(); j++)
        {
            grid[i][j] = row[j];
        }
    }

    grid[0][0] = 's';
    grid[n-1][m-1] = 'd';

    int u, d;

    int heightDiff = n + m - 2;

    int minDist = minDistance(grid, n, m);

    int extra = (minDist - heightDiff) / 2;

    u = heightDiff + extra;
    d = extra;

    int a, b;

    vector<long long> time(k);

    for (int i = 0; i < k; i++)
    {
        cin >> a >> b;
        time[i] = (long long)u * a + (long long)d * b;
    }

    long long int minTime = 9223372036854775807;

    for (int i = 0; i < k; i++)
    {
        if (minTime > time[i])
        {
            minTime = time[i];
        }
    }

    int count = 0;

    for (int i = 0; i < k; i++)
    {
        if (time[i] == minTime)
        {
            count++;
        }
    }

    cout << minTime << " " << count << endl;
}