#include #include #include using namespace std; struct Block { Block() : top(-1), bottom(-1),left(-1),right(-1) {} int top; int bottom; int left; int right; }; int hop[(1<<10) * (1<<10)]; int main(int argc, char* argv[]) { // Retrieve data int W,H,N; cin >> W >> H >> N; vector > paths(N); for (int i = 0; i < N; i++) { int m; cin >> m; for (int j = 0; j < m+1; j++) { int b; cin >> b; paths[i].push_back(b); } } // Initialize the path for each block int nblocks = W * H; vector blocks(nblocks); for (int i = 0; i < N; i++) { vector path = paths[i]; int size = path.size(); for (int j = 0; j < size-1; j++) { int start = path[j]; int end = path[j+1]; if (end < start) { int temp = start; start = end; end = temp; } // the starting point and the ending point are in the same row if (start/W == end/W) { for (int k = start; k <= end; k++) { if (k == start) { blocks[k].right = k+1; } else if (k == end) { blocks[k].left = k-1; } else { blocks[k].left = k-1; blocks[k].right = k+1; } } } // the starting point and the ending point are NOT in the same row else { for (int k = start; k <= end; k+=W) { if (k == start) { blocks[k].top = k+W; } else if (k == end) { blocks[k].bottom = k-W; } else { blocks[k].bottom = k-W; blocks[k].top = k+W; } } } } } // Do BFS to search for a path hop[0] = 1; queue que; que.push(0); int solution = -1; while (!que.empty()) { int current = que.front(); que.pop(); if (current == nblocks-1) { break; } Block block = blocks[current]; int directions[] = {block.top, block.bottom, block.left, block.right}; for (int i = 0; i < sizeof(directions)/sizeof(int); i++) { if (directions[i] != -1 && hop[directions[i]] == 0) { que.push(directions[i]); hop[directions[i]] = hop[current] + 1; } } } solution = hop[nblocks-1]; if (solution == 0) { cout << "Odekakedekinai.." << endl; } else { cout << solution-1 << endl; } }