#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; } }; int field[MAX_H][MAX_W][2]; bool walking[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){ field[fromY][fromX][0]++; field[toY][toX][0]--; }else if(fromX < toX){ field[fromY][fromX][1]++; field[toY][toX][1]--; }else if(fromY > toY){ field[fromY][fromX][0]--; field[toY][toX][0]++; }else{ field[fromY][fromX][1]--; field[toY][toX][1]++; } } void cleanField(){ int valuesW[w]; int valuesH[h]; memset(valuesW, 0, sizeof(valuesW)); memset(valuesH, 0, sizeof(valuesH)); for(int y = 0; y < h; y++){ for(int x = 0; x < w; x++){ if(y > 0 && valuesW[x] > 0){ walking[y-1][x][3] = true; walking[y][x][0] = true; } if(x > 0 && valuesH[y] > 0){ walking[y][x-1][2] = true; walking[y][x][1] = true; } valuesW[x] += field[y][x][0]; valuesH[y] += field[y][x][1]; } } } int main(){ memset(field, 0, sizeof(field)); memset(walking, false, sizeof(walking)); cin >> w >> h >> n; for(int i = 0; i < n; i++){ int m; scanf("%d", &m); int bp = 0; int p = 0; for(int j = 0; j < m+1; j++){ bp = p; scanf("%d", &p); if(j > 0){ walk(bp, p); } } } cleanField(); 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); continue; } 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(walking[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; }