#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; const int MAX_H = 1000; const int MAX_W = 1000; const int DY[4] = {-1, 0, 0, 1}; const int DX[4] = { 0,-1, 1, 0}; struct Coord { int y; int x; int dist; Coord(int y, int x, int dist){ this->y = y; this->x = x; this->dist = dist; } }; bool field[MAX_H][MAX_W][4]; int w, h, n; void walk(int from, int to){ int fromY = from/w; int fromX = from%w; int toY = to/w; int toX = to%w; if(fromY < toY){ for(int y = fromY+1; y <= toY; y++){ field[y-1][fromX][3] = true; field[y][toX][0] = true; } }else if(fromX < toX){ for(int x = fromX+1; x <= toX; x++){ field[fromY][x-1][2] = true; field[toY][x][1] = true; } }else if(fromY > toY){ for(int y = toY+1; y <= fromY; y++){ field[y][fromX][0] = true; field[y-1][toX][3] = true; } }else{ for(int x = toX+1; x <= fromX; x++){ field[fromY][x][1] = true; field[toY][x-1][2] = true; } } } int main(){ memset(field, false, sizeof(field)); cin >> w >> h >> n; for(int i = 0; i < n; i++){ int m; cin >> m; int bp = 0; int p = 0; for(int j = 0; j < m+1; j++){ bp = p; cin >> p; if(j > 0){ walk(bp, p); } } } queue que; que.push(Coord(0, 0, 0)); int minDist = INT_MAX; map checkList; while(!que.empty()){ Coord coord = que.front(); que.pop(); int z = coord.y * w + coord.x; if(checkList[z]) continue; checkList[z] = true; if(h*w-1 == z){ minDist = min(minDist, coord.dist); } for(int i = 0; i < 4; i++){ int ny = coord.y + DY[i]; int nx = coord.x + DX[i]; if(ny < 0 || h <= ny || nx < 0 || w <= nx) continue; if(field[coord.y][coord.x][i]){ que.push(Coord(ny, nx, coord.dist+1)); } } } if (minDist == INT_MAX){ cout << "Odekakedekinai.." << endl; }else{ cout << minDist << endl; } return 0; }