#include #include #include #include #include using namespace std; const int N = 1010; struct D { int row, col, cost; D(int row, int col, int cost) : row(row), col(col), cost(cost) {} }; void display(int rows, int cols, int g[][N][N]) { puts("--- row ---"); for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { printf(" %d", g[0][i][j]); } puts(""); } puts("--- col ---"); for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { printf(" %d", g[1][i][j]); } puts(""); } } int calc(int rows, int cols, int g[][N][N]) { queue q; q.push(D(0, 0, 0)); static int used[N][N] = {}; while (!q.empty()) { D d = q.front(); q.pop(); // printf("r:%d c:%d cost:%d\n", d.row, d.col, d.cost); if (d.row == rows-1 && d.col == cols-1) return d.cost; if (used[d.row][d.col]++) continue; // 上 if (d.row > 0 && g[0][d.row-1][d.col] > 0) q.push(D(d.row-1, d.col, d.cost+1)); // 下 if (d.row+1 < rows && g[0][d.row][d.col] > 0) q.push(D(d.row+1, d.col, d.cost+1)); // 右 if (d.col+1 < cols && g[1][d.row][d.col] > 0) q.push(D(d.row, d.col+1, d.cost+1)); // 左 if (d.col > 0 && g[1][d.row][d.col-1] > 0) q.push(D(d.row, d.col-1, d.cost+1)); } return -1; } int main() { int w, h, n; scanf("%d %d %d", &w, &h, &n); static int g[2][N][N] = {}; // [行or列どちら方向か][行][列] vector > cmap; for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) cmap.push_back(make_pair(i, j)); for (int i = 0; i < n; i++) { int m; scanf("%d", &m); int fm; scanf("%d", &fm); for (int j = 0; j < m; j++) { int to; scanf("%d", &to); // printf("%d -> %d\n", fm, to); int r1 = cmap[fm].first; int c1 = cmap[fm].second; int r2 = cmap[to].first; int c2 = cmap[to].second; // printf("(%d %d) -> (%d %d)\n", r1, c1, r2, c2); if (r1 != r2) { assert(c1 == c2); int fm = min(r1, r2); int to = max(r1, r2); g[0][fm][c1]++; g[0][to][c1]--; } else if (c1 != c2) { assert(r1 == r2); int fm = min(c1, c2); int to = max(c1, c2); g[1][r1][fm]++; g[1][r1][to]--; } else assert(false); fm = to; } } // 行方向を足し上げる for (int c = 0; c < w; c++) { for (int r = 1; r < h; r++) { g[0][r][c] += g[0][r-1][c]; } } // 列方向を足し上げる for (int r = 0; r < h; r++) { for (int c = 1; c < w; c++) { g[1][r][c] += g[1][r][c-1]; } } // display(h, w, g); int ans = calc(h, w, g); if (ans == -1) { puts("Odekakedekinai.."); } else { printf("%d\n", ans); } }