#include #include #include #include #include #include #include #include #include using namespace std; typedef pair PII; const int UP = 1; const int DOWN = 1 << 1; const int RIGHT = 1 << 2; const int LEFT = 1 << 3; string bin_str(int n) { stringstream ss; ss << static_cast >(n); return ss.str(); } void show(vector &v) { for (auto e : v) { printf("%2d ", e); } printf("\n"); } int main() { int w, h, n; scanf("%d %d %d", &w, &h, &n); vector horizontal(w*h, 0); vector vertical(w*h, 0); for (int i = 0; i < n; i++) { int m, b, b_prev; scanf("%d %d", &m, &b_prev); for (int j = 1; j <= m; j++) { scanf("%d", &b); int big = max(b, b_prev); int small = min(b, b_prev); if (big - small < w) { horizontal[small] += 1; horizontal[big] -= 1; } else { vertical[small] += 1; vertical[big] -= 1; } b_prev = b; } } // show(horizontal); // show(vertical); vector connect(w * h, 0); for (int i = 0; i < h; i++) { int l = i * w; int r = (i + 1) * w - 1; // printf("lr %d %d\n", r, l); int ok_right = 0; for (int j = l; j <= r; j++) { ok_right += horizontal[j]; if (ok_right > 0) { connect[j] |= RIGHT; } } int ok_left = 0; for (int j = r; j >= l; j--) { ok_left += horizontal[j]; if (ok_left < 0) { connect[j] |= LEFT; } } } for (int i = 0; i < w; i++) { int d = i; int u = (h - 1) * w + i; int ok_up = 0; for (int j = d; j <= u; j += w) { ok_up += vertical[j]; if (ok_up > 0) { connect[j] |= UP; } } int ok_down = 0; for (int j = u; j >= d; j -= w) { ok_down += vertical[j]; if (ok_down < 0) { connect[j] |= DOWN; } } } // for (int i = 0; i < w * h; i++) { // printf("connect %d %s\n", i, bin_str(connect[i]).c_str()); // } vector memo(w * h, -1); queue que; int goal = w * h - 1; memo[0] = 0; que.push(0); int masks[4] = {UP, DOWN, RIGHT, LEFT}; int to_next[4] = {w, -w, 1, -1}; while (!que.empty()) { auto now = que.front(); que.pop(); // printf("now %d\n", now); if (now == goal) { break; } for (int i = 0; i < 4; i++) { if (connect[now] & masks[i]) { auto next = now + to_next[i]; // printf("next %d %d\n", next, memo[next]); if (memo[next] == -1) { memo[next] = memo[now] + 1; que.push(next); } } } } if (memo[goal] == -1) { cout << "Odekakedekinai.." << endl; } else { cout << memo[goal] << endl; } return 0; }