#include #include #include #include #include #include #include #include #include using namespace std; const int UP = 1; const int DOWN = 1 << 1; const int RIGHT = 1 << 2; const int LEFT = 1 << 3; const int INF = 1e9; string bin_str(int n) { stringstream ss; ss << static_cast >(n); return ss.str(); } int main() { int w, h, n, m, in_b; cin >> w >> h >> n; vector> b(n); for (int i = 0; i < n; i++) { cin >> m; for (int j = 0; j <= m; j++) { cin >> in_b; b[i].emplace_back(in_b); } } // up down right left の順にbit vector connect(w * h, 0); for (int i = 0; i < n; i++) { if (b[i].size() < 2) { continue; } for (int j = 1; j < b[i].size(); j++) { int big = max(b[i][j - 1], b[i][j]); int small = min(b[i][j - 1], b[i][j]); if (big - small < w) { connect[small] |= RIGHT; connect[big] |= LEFT; for (int k = small + 1; k < big; k++) { connect[k] |= (RIGHT | LEFT); } } else { connect[small] |= UP; connect[big] |= DOWN; for (int k = small + w; k < big; k += w) { connect[k] |= (UP | 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, 1e9); 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 place = que.front(); que.pop(); // printf("place %d\n", place); if (place == goal) { break; } for (int i = 0; i < 4; i++) { if (connect[place] & masks[i]) { auto next = place + to_next[i]; // printf("next %d %d\n", next, memo[next]); if (memo[next] > memo[place] + 1) { que.push(place + to_next[i]); memo[next] = memo[place] + 1; } } } } if (memo[goal] == INF) { cout << "Odekakedekinai.." << endl; } else { cout << memo[goal] << endl; } return 0; }