#include #include #include using namespace std; struct Node { int x; int y; int cost; }; int x_axis[1000][1000]; int y_axis[1000][1000]; int dp[1000][1000]; int dx[] = { -1, 1, 0, 0 }; int dy[] = { 0, 0, -1, 1 }; int main() { int w, h, n; cin >> w >> h >> n; int b[1001]; for (int i = 0; i < n; i++) { int m; cin >> m; for (int k = 0; k < m + 1; k++) { cin >> b[k]; } for (int k = 0; k < m; k++) { int small_no = b[k]; int large_no = b[k + 1]; if (small_no > large_no) { swap(small_no, large_no); } if ((large_no - small_no) % w == 0) { int x = small_no % w; y_axis[x][small_no / w]++; y_axis[x][large_no / w]--; } else { int y = small_no / w; x_axis[y][small_no % w]++; x_axis[y][large_no % w]--; } } } for (int x = 0; x < w; x++) { for (int y = 0; y < h - 1; y++) { y_axis[x][y + 1] += y_axis[x][y]; } } for (int y = 0; y < h; y++) { for (int x = 0; x < w - 1; x++) { x_axis[y][x + 1] += x_axis[y][x]; } } for (int y = 0; y < h; y++) { for (int x = 0; x < w; x++) { dp[y][x] = INT_MAX; } } dp[0][0] = 0; queue nodes; nodes.emplace(Node{ 0, 0, 0 }); while (!nodes.empty()) { Node node = nodes.front(); nodes.pop(); for (int i = 0; i < 4; i++) { int nx = node.x + dx[i]; int ny = node.y + dy[i]; if(ny < 0 || ny >= h || nx < 0 || nx >= w) continue; int x, y; switch (i) { case 0: case 1: // 横 x = (nx + node.x) / 2; if (x_axis[ny][x] <= 0) continue; break; case 2: case 3: // 縦 y = (ny + node.y) / 2; if (y_axis[nx][y] <= 0) continue; break; default: break; } int next_cost = node.cost + 1; if (dp[ny][nx] <= next_cost) continue; dp[ny][nx] = next_cost; nodes.emplace(Node{ nx, ny, next_cost }); } } int result = dp[h - 1][w - 1]; if (result == INT_MAX) { cout << "Odekakedekinai.." << endl; } else { cout << result << endl; } return 0; }