#include #include #include #include #include #include using namespace std; void read_data(int W, int H, int N, vector & map_hrzn, vector & map_vrtc); int solve(int W, int H, const vector & map_hrzn, const vector & map_vrtc); int main() { ios::sync_with_stdio(false); int W = 0; int H = 0; int N = 0; cin >> W >> H >> N; vector map_hrzn(W * H, 0); vector map_vrtc(W * H, 0); read_data(W, H, N, map_hrzn, map_vrtc); partial_sum(map_hrzn.begin(), map_hrzn.end(), map_hrzn.begin()); partial_sum(map_vrtc.begin(), map_vrtc.end(), map_vrtc.begin()); auto ans = solve(W, H, map_hrzn, map_vrtc); if (ans == -1){ cout << "Odekakedekinai.." << endl; }else{ cout << ans << endl; } return 0; } void read_data(int W, int H, int N, vector & map_hrzn, vector & map_vrtc){ int M = 0; for (int i = 0; i != N; ++i){ cin >> M; int next_b, prev_b, next_w, next_h, prev_w, prev_h; cin >> prev_b; prev_w = prev_b % W; prev_h = prev_b / W; for (int m = 0; m != M; ++m){ cin >> next_b; next_w = next_b % W; next_h = next_b / W; if (prev_w == next_w){ if (prev_h < next_h){ map_vrtc[prev_w * H + prev_h] += 1; map_vrtc[next_w * H + next_h] -= 1; }else{ map_vrtc[prev_w * H + prev_h] -= 1; map_vrtc[next_w * H + next_h] += 1; } }else{ if (prev_b < next_b){ map_hrzn[prev_b] += 1; map_hrzn[next_b] -= 1; }else{ map_hrzn[prev_b] -= 1; map_hrzn[next_b] += 1; } } prev_w = next_w; prev_h = next_h; prev_b = next_b; } } } int solve(int W, int H, const vector & map_hrzn, const vector & map_vrtc){ stack prev_que; stack next_que; vector visited(H * W, false); const int goal = H * W - 1; prev_que.push(0); for (int steps = 0; steps != H * W; ++steps){ while (not prev_que.empty()){ auto b_hrzn = prev_que.top(); if (b_hrzn == goal) return steps; prev_que.pop(); int w = b_hrzn % W; int h = b_hrzn / W; int b_vrtc = w * H + h; if (w and map_hrzn[b_hrzn - 1] and not visited[b_hrzn - 1]){ next_que.push(b_hrzn - 1); visited[b_hrzn - 1] = true; } if (w != W - 1 and map_hrzn[b_hrzn] and not visited[b_hrzn + 1]){ next_que.push(b_hrzn + 1); visited[b_hrzn + 1] = true; } if (h and map_vrtc[b_vrtc - 1] and not visited[b_hrzn - W]){ next_que.push(b_hrzn - W); visited[b_hrzn - W] = true; } if (h != H - 1 and map_vrtc[b_vrtc] and not visited[b_hrzn + W]){ next_que.push(b_hrzn + W); visited[b_hrzn + W] = true; } } swap(prev_que, next_que); } return -1; }