#include #include #include template class Heap { public: Heap(const int &n) :vector(n + 1), idx(0) {}; void insert_value(const T &val) { vector.at(++idx) = val; bottom_up_normalize(idx); } T pop() { auto res = vector.at(1); vector.at(1) = vector.at(idx); vector.at(idx--) = vector.back(); top_down_normalize(1); return res; } int size() const { return idx; } T top() const { return vector.at(1); } private: std::vector vector; int idx; void bottom_up_normalize(const int &i) { if (i != 1) { if (vector.at(i) < vector.at(i / 2)) { auto temp = vector.at(i / 2); vector.at(i / 2) = vector.at(i); vector.at(i) = temp; bottom_up_normalize(i / 2); } } } void top_down_normalize(const int &i) { int next = get(i); if (vector.at(next) < vector.at(i)) { auto temp = vector.at(next); vector.at(next) = vector.at(i); vector.at(i) = temp; top_down_normalize(next); } } int get(const int &n) const { if (n * 2 + 1 <= idx) { return (vector.at(n * 2 + 1) < vector.at(n * 2)) ? n * 2 + 1 : n * 2; } else if (n * 2 <= idx) { return n * 2; } else { return n; } } }; class Cell { public: Cell(const int &ax = 0, const int &ay = 0) :state{ 0 }, x{ ax }, y{ ay } {}; bool is_neighbor(const Cell &other) const { return (abs(x - other.x) + abs(y - other.y)) == 1; } void set_path(Cell &from) { if (is_neighbor(from)) { if (x == from.x) { if (y > from.y) { state |= up; from.state |= down; } else { state |= down; from.state |= up; } } else { if (x > from.x) { state |= left; from.state |= right; } else { state |= right; from.state |= left; } } } } std::vector> get_neighbor() const { std::vector> res; for (const auto &p : { std::make_pair(x + 1, y), std::make_pair(x - 1, y), std::make_pair(x, y + 1), std::make_pair(x, y - 1) }) { if (has_path(p.first, p.second)) { res.push_back(p); } } return res; } private: enum { right = 1, down = 2, left = 4, up = 8 }; int state; int x, y; int abs(const int &n) const { return n > 0 ? n : -n; } bool has_path(const int &cellx, const int &celly) const { if ((abs(x - cellx) + abs(y - celly)) == 1) { if (x == cellx) { if (y > celly) { return (state & up) != 0; } else { return (state & down) != 0; } } else { if (x > cellx) { return (state & left) != 0; } else { return (state & right) != 0; } } } else { return false; } } }; struct Reach_time { int x, y; int time; Reach_time(const int &ax = 0, const int &ay = 0, const int &at = 0) :x{ ax }, y{ ay }, time{ at } {}; bool operator<(const Reach_time &other) const { return time < other.time; } }; int daijkstra(const std::vector> &map) { Heap heap(map.size() * map.at(0).size() * 4); std::vector> memo(map.size(), std::vector(map.at(0).size(), INT_MAX)); heap.insert_value(Reach_time(0, 0, 0)); memo.at(0).at(0) = 0; while (((heap.top().x != map.size() - 1) || (heap.top().y != map.at(0).size() - 1)) && heap.size() != 0) { auto rtime = heap.pop(); const auto &cell = map.at(rtime.y).at(rtime.x); for (const auto &neighbor : cell.get_neighbor()) { if (memo.at(neighbor.first).at(neighbor.second) > rtime.time + 1) { memo.at(neighbor.first).at(neighbor.second) = rtime.time + 1; heap.insert_value(Reach_time(neighbor.first, neighbor.second, rtime.time + 1)); } } } if (heap.size() == 0) { return 0; } else { return heap.top().time; } } int main() { int w, h, n; std::cin >> w >> h >> n; std::vector> map(h, std::vector(w)); for (auto y = 0; y < h; ++y) { for (auto x = 0; x < w; ++x) { map.at(y).at(x) = Cell(x, y); } } for (auto i = 0; i < n; ++i) { int m; std::cin >> m; int prev; std::cin >> prev; for (int b; m > 0; --m) { std::cin >> b; if (prev % w == b % w) { auto min = prev / w > b / w ? b / w : prev / w; auto max = prev / w > b / w ? prev / w : b / w; for (; min < max; ++min) { map.at(min).at(prev % w).set_path(map.at(min + 1).at(prev % w)); } } else { auto min = prev % w > b % w ? b % w : prev % w; auto max = prev % w > b % w ? prev % w : b % w; for (; min < max; ++min) { map.at(prev / w).at(min).set_path(map.at(prev / w).at(min + 1)); } } prev = b; } } auto res = daijkstra(map); if (res == 0) { std::cout << "Odekakedekinai.." << std::endl; } else { std::cout << res << std::endl; } return 0; }