#include #include #include using namespace std; struct Block { Block() : up(0), down(0),left(0),right(0) {} int up; int down; int left; int right; }; vector paths[(1<<10) * (1<<10)]; int hops[(1<<10) * (1<<10)]; int visit[(1<<10) * (1<<10)]; int main(int argc, char* argv[]) { // Retrieve data int W,H,N; cin >> W >> H >> N; // Initialize the path for each block int nblocks = W * H; vector blocks(nblocks); for (int i = 0; i < N; i++) { int m; cin >> m; int prev = -1; for (int j = 0; j < m+1; j++) { int n; cin >> n; if (prev != -1) { int b = min(n, prev); int d = abs(n - prev); if (d < W) { blocks[b].right = max(blocks[b].right, d); } else { blocks[b].up = max(blocks[b].up, d/W); } } prev = n; } } for (int i = 0; i < H; i++) { for (int j = 0; j < W; j++) { int b = i * W + j; if (i) { blocks[b].up = max(blocks[b].up, blocks[b-W].up-1); } if (j) { blocks[b].right = max(blocks[b].right, blocks[b-1].right-1); } if (blocks[b].up && i < H-1) { paths[b].push_back(b+W); paths[b+W].push_back(b); } if (blocks[b].right && j < W-1) { paths[b].push_back(b+1); paths[b+1].push_back(b); } } } // Do BFS to search for a path for (int i = 0; i < nblocks; i++) { hops[i] = 1<<20; } hops[0] = 0; visit[0] = 1; queue que; que.push(0); while (!que.empty()) { int current = que.front(); que.pop(); vector path = paths[current]; for (int i = 0; i < path.size(); i++) { int p = path[i]; if (visit[p] == 0) { visit[p] = 1; hops[p] = hops[current] + 1; que.push(p); } } } if (visit[nblocks-1]) { cout << hops[nblocks-1] << endl; } else { cout << "Odekakedekinai.." << endl; } }