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
#if defined(EMBE_DEBUG) && !defined(NDEBUG)
#include "embe-debug.hpp"
#else
#define LOG_INDENT(...) do {} while (false)
#define LOG(...) do {} while (false)
#define DUMP(...) do {} while (false)
#endif

#include <cassert>
#include <iostream>
#include <optional>
#include <string>
#include <utility>
#include <vector>
using namespace std;

namespace {

int bfs(vector<string> const& map, int sx, int sy, int tx, int ty)
{
  int n = map.size();
  int m = map[0].size();
  vector<vector<optional<int>>> dist(n, vector<optional<int>>(m));
  vector<pair<int, int>> cur = {{sx, sy}};
  vector<pair<int, int>> next;
  dist[sx][sy] = 0;
  while (!dist[tx][ty]) {
    int i = 0;
    while (i < int(cur.size())) {
      auto get = [&](int x, int y) {
        if (x < 0 || y < 0 || x >= n || y >= m) return 'X';
        return map[x][y];
      };
      auto add = [&](auto& v, int x, int y, int d) {
        if (dist[x][y] && *dist[x][y] <= d) return;
        dist[x][y] = d;
        v.emplace_back(x, y);
      };
      auto [x, y] = cur[i];
      auto d = *dist[x][y];
      if (get(x + 1, y) == '.') add(cur, x + 1, y, d);
      if (get(x, y + 1) == '.') add(cur, x, y + 1, d);
      if (get(x - 1, y) == '.') add(next, x - 1, y, d + 1);
      if (get(x, y - 1) == '.') add(next, x, y - 1, d + 1);
      ++i;
    }
    swap(next, cur);
    next.clear();
  }
  return *dist[tx][ty];
}

pair<long long, int> solve(vector<string> const& map, vector<pair<int, int>> const& speeds)
{
  int n = map.size();
  int m = map[0].size();
  int d = bfs(map, 0, 0, n - 1, m - 1);
  optional<long long> best_time;
  int best_count = 0;
  for (auto const& [a, b]: speeds) {
    auto time = static_cast<long long>(n + m - 2) * a + static_cast<long long>(d) * (a + b);
    if (!best_time || *best_time > time) {
      best_time = time;
      best_count = 0;
    }
    if (time == *best_time) {
      ++best_count;
    }
  }
  return {*best_time, best_count};
}

}

int main()
{
  iostream::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m, k;
  cin >> n >> m >> k;
  vector<string> map(n);
  for (int i = 0; i < n; ++i) {
    cin >> map[i];
  }

  vector<pair<int, int>> speeds(k);
  for (int i = 0; i < k; ++i) {
    cin >> speeds[i].first >> speeds[i].second;
  }

  auto [time, cnt] = solve(map, speeds);
  cout << time << ' ' << cnt << endl;

  return 0;
}