#include #include #include #include #include #include #include using namespace std; #define FOR(i,a,b) for (int i=(a);i<(b);i++) #define FORR(i,a,b) for (int i=(b)-1;i>=(a);i--) #define REP(i,n) for (int i=0;i<(n);i++) #define RREP(i,n) for (int i=(n)-1;i>=0;i--) #define pb push_back #define ALL(a) (a).begin(),(a).end() #define EPS (1e-10) #define EQ(a,b) (abs((a)-(b)) < EPS) #define PI 3.1415926535 typedef long long ll; typedef pair P; //typedef complex C; const int INF = 99999999; const int MAX_W = 1000; const int MAX_H = 1000; const int MAX_N = 1000; const int MAX_M = 1000; int W, H, N; int B[MAX_M + 1]; int imos1[MAX_H + 1][MAX_W + 1]; // row int imos2[MAX_H + 1][MAX_W + 1]; // col int d[MAX_H][MAX_W]; int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; void mark() { int M; scanf("%d", &M); // vector B(M); // REP(i, M + 1) { // scanf("%d", &B[i]); // } REP(i, MAX_M + 1) B[i] = 0; REP(i, M + 1) { scanf("%d", &B[i]); } REP(i, M) { int r1, c1, r2, c2; r1 = B[i] / H; r2 = B[i + 1] / H; c1 = B[i] % W; c2 = B[i + 1] % W; if(r1 == r2) { // 横に歩いた imos1[r1][min(c1, c2)] = 1; imos1[r1][max(c1, c2) + 1] = -1; } else { // 縦に歩いた imos2[min(r1, r2)][c1] = 1; imos2[max(r1, r2) + 1][c1] = -1; } } } void input() { scanf("%d%d%d", &W, &H, &N); REP(i, N) { mark(); } } void makeField() { REP(i, H) { REP(j, W) { imos1[i][j + 1] += imos1[i][j]; imos2[i + 1][j] += imos2[i][j]; } } } bool inside(int x, int y) { return x >= 0 && x < H && y >= 0 && y < W; } bool canMove(int r1, int c1, int r2, int c2) { if (r1 == r2) { // 横に移動したい // 今いるマスと次に行くマスがどちらも0でないなら移動できる return imos1[r1][c1] * imos1[r2][c2] > 0; } else { return imos2[r1][c1] * imos2[r2][c2] > 0; } } int bfs(int sx, int sy, int gx, int gy) { REP(i, H) REP(j, W) d[i][j] = INF; d[sx][sy] = 0; queue

que; que.push(P(sx, sy)); while (!que.empty()) { P p = que.front(); que.pop(); int x = p.first, y = p.second; if (x == gx && y == gy) break; for (int k = 0; k < 4; k++) { int nx = x + dx[k], ny = y + dy[k]; if (inside(nx, ny) && canMove(x, y, nx, ny)) { que.push(P(nx, ny)); d[nx][ny] = d[x][y] + 1; } } } return d[gx][gy]; } void solve() { makeField(); int ans = bfs(0, 0, H - 1, W - 1); if (ans < INF) { printf("%d\n", ans); } else { printf("Odekakedekinai..\n"); } } int main() { input(); solve(); }