#pragma region include #include <iostream> #include <iomanip> #include <stdio.h> #include <sstream> #include <algorithm> #include <cmath> #include <complex> #include <string> #include <cstring> #include <vector> #include <tuple> #include <queue> #include <complex> #include <set> #include <map> #include <stack> #include <list> #include <fstream> #include <random> //#include <time.h> #include <ctime> #pragma endregion //#include ///////// #define REP(i, x, n) for(int i = x; i < n; ++i) #define rep(i,n) REP(i,0,n) ///////// #pragma region typedef typedef long long LL; typedef long double LD; typedef unsigned long long ULL; #pragma endregion //typedef ////定数 const int INF = (int)1e9; const LL MOD = (LL)1e9+7; const LL LINF = (LL)1e18; const double PI = acos(-1.0); const double EPS = 1e-9; ///////// using namespace::std; vector< vector<int> > Gra; vector<int> dist; void solve(){ int W,H,N; cin >> W >> H >> N; Gra = vector< vector<int> >(W*H); vector< vector<int> > RR(W,vector<int>(H+1,0)); vector< vector<int> > CC(H,vector<int>(W+1,0)); for(int i=0;i<N;++i){//10^3 int M; cin >> M; ++M; vector<int> B(M); for(int j=0;j<M;++j){ cin >> B[j]; } for(int j=1;j<M;++j){//10^3 int u,v; u = B[j-1]; v = B[j]; if( u > v ){ swap(u,v); } if( u%W == v%W ){//縦移動RR int rank = u%W; RR[rank][u/W]++; RR[rank][(v/W)]--; /*for(int k=u+W;k<=v;k+=W){ Gra[k-W].push_back(k); Gra[k].push_back(k-W); }*/ }else{//横移動CC int rank = u/W; CC[rank][u%W]++; CC[rank][(v%W)]--; /*for(int k=u+1;k<=v;++k){ Gra[k-1].push_back(k); Gra[k].push_back(k-1); }*/ } } } for(int c=0;c<W;++c){ if( RR[c][0] > 0 ){ Gra[0*W+c].push_back(1*W+c); Gra[1*W+c].push_back(0*W+c); } for(int r=1;r<H-1;++r){ RR[c][r]+= RR[c][r-1]; if( RR[c][r] > 0 ){ Gra[r*W+c].push_back((r+1)*W+c); Gra[(r+1)*W+c].push_back(r*W+c); } } } for(int r=0;r<H;++r){ if( CC[r][0] > 0 ){ Gra[r*W+0].push_back(r*W+1); Gra[r*W+1].push_back(r*W+0); } for(int c=1;c<W-1;++c){ CC[r][c] += CC[r][c-1]; if( CC[r][c] > 0 ){ Gra[r*W+c].push_back(r*W+c+1); Gra[r*W+c+1].push_back(r*W+c); } } } dist = vector<int>(W*H,INF); vector<bool> visit(W*H, false); queue<int> que; que.push(0);//スタート地点 visit[0] = true; dist[0] = 0; while(!que.empty()){ int now = que.front();que.pop(); int size = Gra[now].size(); for(int i=0;i<size;++i){ int to = Gra[now][i]; if( visit[to] == true ) continue; visit[to] = true; dist[to] = dist[now] + 1; que.push( to ); } } if( dist[W*H-1] == INF ){ cout << "Odekakedekinai.." << endl; }else{ cout << dist[W*H-1] << endl; } } #pragma region main signed main(void){ std::cin.tie(0); std::ios::sync_with_stdio(false); std::cout << std::fixed;//小数を10進数表示 cout << setprecision(16);//小数点以下の桁数を指定//coutとcerrで別 solve(); } #pragma endregion //main()