#include <bits/stdc++.h> #define REP(i,n) for(int _n=(n), i=0;i<_n;++i) #define FOR(i,a,b) for(int i=(a),_b=(b);i<=_b;++i) #define FORD(i,a,b) for(int i=(a),_b=(b);i>=_b;--i) #define TRACE(x) cerr << "TRACE(" #x ")" << endl; #define DEBUG(x) cerr << #x << " = " << (x) << endl; typedef long long LL; typedef unsigned long long ULL; void init_io() { std::cin.tie(nullptr); std::ios::sync_with_stdio(false); } class Map { public: Map(); // up, down std::pair<int, int> shortest_path(); int num_people() const { return m_num_people; } private: int from_coord(int x, int y) const { return y * sx + x; } int m_num_people; int sx, sy; // including borders int dirs[4]; std::vector<char> visited; }; Map::Map() { std::cin >> sy >> sx >> m_num_people; sy += 2; sx += 2; dirs[0] = 1; dirs[1] = sx; dirs[2] = -1; dirs[3] = -sx; visited.assign(sx * sy, 1); std::string line; FOR(y, 1, sy-2) { std::cin >> line; assert(int(line.size()) == sx-2); FOR(x, 1, sx-2) visited[from_coord(x, y)] = line[x-1] == 'X'; } } // { up, down } std::pair<int, int> Map::shortest_path() { std::vector<int> beam, beam_next; beam.reserve(sx * sy); beam_next.reserve(sx * sy); const int start = from_coord(1,1); const int goal = from_coord(sx-2, sy-2); int distance = 0; beam.push_back(start); assert(!visited[start]); visited[start] = 1; for (;;) { assert(!beam.empty()); for (int a : beam) { if (a == goal) goto done; for (int dir: dirs) { int b = a + dir; if (!visited[b]) { beam_next.push_back(b); visited[b] = 1; } } } beam.clear(); beam.swap(beam_next); ++distance; } done: const int straight_distance = (sx-3) + (sy-3); assert((distance - straight_distance) % 2 == 0); const int extra = (distance - straight_distance) / 2; return {straight_distance + extra, extra}; } // { best_time, num_best } std::pair<LL, int> process_people(int num_people, int up_steps, int down_steps) { LL best_time = std::numeric_limits<LL>::max(); int num_best = 0; REP(i, num_people) { int time_up, time_down; std::cin >> time_up >> time_down; LL t = LL(time_up) * up_steps + LL(time_down) * down_steps; if (t < best_time) { best_time = t; num_best = 1; } else if (t == best_time) { ++num_best; } } return {best_time, num_best}; } int main() { init_io(); Map map; auto [up, down] = map.shortest_path(); auto [best_time, num_best] = process_people(map.num_people(), up, down); std::cout << best_time << " " << num_best << "\n"; }
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 <bits/stdc++.h> #define REP(i,n) for(int _n=(n), i=0;i<_n;++i) #define FOR(i,a,b) for(int i=(a),_b=(b);i<=_b;++i) #define FORD(i,a,b) for(int i=(a),_b=(b);i>=_b;--i) #define TRACE(x) cerr << "TRACE(" #x ")" << endl; #define DEBUG(x) cerr << #x << " = " << (x) << endl; typedef long long LL; typedef unsigned long long ULL; void init_io() { std::cin.tie(nullptr); std::ios::sync_with_stdio(false); } class Map { public: Map(); // up, down std::pair<int, int> shortest_path(); int num_people() const { return m_num_people; } private: int from_coord(int x, int y) const { return y * sx + x; } int m_num_people; int sx, sy; // including borders int dirs[4]; std::vector<char> visited; }; Map::Map() { std::cin >> sy >> sx >> m_num_people; sy += 2; sx += 2; dirs[0] = 1; dirs[1] = sx; dirs[2] = -1; dirs[3] = -sx; visited.assign(sx * sy, 1); std::string line; FOR(y, 1, sy-2) { std::cin >> line; assert(int(line.size()) == sx-2); FOR(x, 1, sx-2) visited[from_coord(x, y)] = line[x-1] == 'X'; } } // { up, down } std::pair<int, int> Map::shortest_path() { std::vector<int> beam, beam_next; beam.reserve(sx * sy); beam_next.reserve(sx * sy); const int start = from_coord(1,1); const int goal = from_coord(sx-2, sy-2); int distance = 0; beam.push_back(start); assert(!visited[start]); visited[start] = 1; for (;;) { assert(!beam.empty()); for (int a : beam) { if (a == goal) goto done; for (int dir: dirs) { int b = a + dir; if (!visited[b]) { beam_next.push_back(b); visited[b] = 1; } } } beam.clear(); beam.swap(beam_next); ++distance; } done: const int straight_distance = (sx-3) + (sy-3); assert((distance - straight_distance) % 2 == 0); const int extra = (distance - straight_distance) / 2; return {straight_distance + extra, extra}; } // { best_time, num_best } std::pair<LL, int> process_people(int num_people, int up_steps, int down_steps) { LL best_time = std::numeric_limits<LL>::max(); int num_best = 0; REP(i, num_people) { int time_up, time_down; std::cin >> time_up >> time_down; LL t = LL(time_up) * up_steps + LL(time_down) * down_steps; if (t < best_time) { best_time = t; num_best = 1; } else if (t == best_time) { ++num_best; } } return {best_time, num_best}; } int main() { init_io(); Map map; auto [up, down] = map.shortest_path(); auto [best_time, num_best] = process_people(map.num_people(), up, down); std::cout << best_time << " " << num_best << "\n"; } |