#include #include #include #include #include using namespace std; const int DIR_NONE = 0; const int DIR_LEFT = 1; const int DIR_UP = 2; const int DIR_RIGHT = 4; const int DIR_DOWN = 8; struct Node { int y; int x; int cost; }; struct DirInfo { int dir; int dy; int dx; }; int main() { int w, h, n; cin >> w >> h >> n; vector> town(h); for (auto& row : town) { row.resize(w, DIR_NONE); } for (int i = 0; i < n; i++) { int stop_count, current_no; cin >> stop_count >> current_no; for (int k = 0; k < stop_count; k++) { int next_no, small_no, large_no; cin >> next_no; if (current_no > next_no) { small_no = next_no; large_no = current_no; } else { small_no = current_no; large_no = next_no; } int sy = small_no / w; int sx = small_no - sy * w; int ly = large_no / w; int lx = large_no - ly * w; if ((large_no - small_no) % w == 0) { town[sy][sx] |= DIR_DOWN; town[ly][sx] |= DIR_UP; for (int m = sy + 1; m <= ly - 1; m++) { town[m][sx] |= DIR_UP | DIR_DOWN; } } else { town[sy][sx] |= DIR_RIGHT; town[sy][lx] |= DIR_LEFT; for (int m = sx + 1; m <= lx - 1; m++) { town[sy][m] |= DIR_LEFT | DIR_RIGHT; } } current_no = next_no; } } vector> dp(h); for (auto& row : dp) { row.resize(w, INT_MAX); } dp[0][0] = 0; vector dirs = { DirInfo { DIR_LEFT, 0, -1}, DirInfo { DIR_UP, -1, 0}, DirInfo { DIR_RIGHT, 0, 1}, DirInfo { DIR_DOWN, 1, 0} }; queue nodes; nodes.emplace(Node{ 0, 0, 0 }); while (!nodes.empty()) { Node node = nodes.front(); nodes.pop(); for (int i = 0; i < dirs.size(); i++) { DirInfo info = dirs[i]; int ny = node.y + info.dy; int nx = node.x + info.dx; if (ny < 0 || ny >= h || nx < 0 || nx >= w) continue; if ((town[node.y][node.x] & info.dir) == 0) continue; int next_cost = node.cost + 1; if (dp[ny][nx] <= next_cost) continue; dp[ny][nx] = next_cost; nodes.emplace(Node{ ny, nx, next_cost }); } } int result = dp[h - 1][w - 1]; if (result == INT_MAX) { cout << "Odekakedekinai.." << endl; } else { cout << result << endl; } return 0; }