#include #include #include #include #define rep(i,a,b) for(int i=(a);i<(b);i++) #define pb push_back using namespace std; int main(void) { int w, h, n, t1, t2, x1, y1, x2, y2, x, y, i, j; cin >> w >> h >> n; vector v; vector > lt; rep(i, 0, n) { v.clear(); cin >> t1; rep(j, 0, t1+1) { cin >> t2; v.pb(t2); } lt.pb(v); } int bf[4] = {1,2,4,8}; // N E W S vector > dp(1000, vector(1000, 0)); vector > mp(1000, vector(1000, 0)); for(auto vec : lt) { rep(j, 0, (int)vec.size()-1) { y1 = vec[j]/w; x1 = vec[j]%w; y2 = vec[j+1]/w; x2 = vec[j+1]%w; if(y1 == y2) { if(x1 < x2) { rep(i,0,x2-x1) { mp[y1][x1+i] |= bf[1]; mp[y1][x1+1+i] |= bf[2]; } } else if(x1 > x2) { rep(i,0,x1-x2) { mp[y1][x1-i] |= bf[2]; mp[y1][x1-1-i] |= bf[1]; } } } else if(x1 == x2) { if(y1 < y2) { rep(i,0,y2-y1) { mp[y1+i][x1] |= bf[0]; mp[y1+1+i][x1] |= bf[3]; } } else if(y1 > y2) { rep(i,0,y1-y2) { mp[y1-i][x1] |= bf[3]; mp[y1-1-i][x1] |= bf[0]; } } } } } pair p; queue > q; q.push(pair(0,0)); int ym[4] = {1, 0, 0, -1}; int xm[4] = {0, 1, -1, 0}; while(q.size()) { p = q.front(); y = p.first; x = p.second; q.pop(); rep(i,0,4) { if(!(mp[y][x] & bf[i])) continue; if(dp[y + ym[i]][x + xm[i]] == 0 || dp[ y+ym[i] ][ x+xm[i] ] > dp[y][x]+1) { dp[y + ym[i]][x + xm[i]] = dp[y][x] + 1; p.first = y+ym[i]; p.second = x+xm[i]; q.push(p); } } } dp[h-1][w-1]? cout << dp[h-1][w-1] << endl : cout << "Odekakedekinai.." << endl; return 0; }