#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef pair pint; typedef vector vint; typedef vector vpint; #define mp make_pair #define fi first #define se second #define all(v) (v).begin(),(v).end() #define rep(i,n) for(int i=0;i<(n);i++) #define REP(i,n) for (int i=(n)-1;i>=0;i--) #define reps(i,f,n) for(int i=(f);i<(n);i++) #define REPS(i,f,n) for (int i=(f)-1;i>=(n);i--) int dx[4] = {1, 0, 0, -1}; int dy[4] = {0, 1, -1, 0}; int main(void){ int w, h, n; cin >> w >> h >> n; int board[1001][1001]; rep(i, h){ rep(j, w) board[i][j] = 0; } //大人が通った場所を1に int m; rep(i, n){ cin >> m; rep(i, m + 1){ int num; cin >> num; int dy_tmp = num / w; int dx_tmp = num % w; board[dy_tmp][dx_tmp] = 1; } } //子供がどこを通るかを確かめる queue q;//現在の位置を入れていく q.push(mp(0, 0)); int cnt = 0; int record[1010][1010]; rep(i, h){ rep(j, w) record[i][j] = 0; } while(!q.empty()){ pint tmp = q.front(); //tmp(y, x)情報 q.pop(); rep(i, 4){ int dy_board = tmp.fi + dy[i]; int dx_board = tmp.se + dx[i]; if (0 <= dx_board && dx_board <= w - 1 && 0 <= dy_board && dy_board <= h - 1 && board[tmp.fi][tmp.se] != 0){ if (board[dy_board][dx_board] == 1 && record[dy_board][dx_board] == 0){ record[dy_board][dx_board] = record[tmp.fi][tmp.se] + 1; q.push(mp(dy_board, dx_board)); } } if (dy_board == h - 1 && dx_board == w - 1){ printf("%d\n", record[h - 1][w - 1]); return 0; } } } printf("Odekakedekinai..\n"); return 0; }