#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; int minDist(const vector& plane, char wall, int y1, int x1, int y2, int x2) { int dy[] = {0, 0, -1, 1}; int dx[] = {-1, 1, 0, 0}; int h = plane.size(); int w = plane[0].size(); queue > q; vector > check(h, vector(w, false)); q.push(make_pair(y1, x1)); check[y1][x1] = true; int ret = 0; while(!q.empty()){ queue > q1; while(!q.empty()){ int y = q.front().first; int x = q.front().second; q.pop(); if(y == y2 && x == x2) return ret; for(int i=0; i<4; ++i){ int y0 = y + dy[i]; int x0 = x + dx[i]; if(plane[y0][x0] != wall && !check[y0][x0]){ q1.push(make_pair(y0, x0)); check[y0][x0] = true; } } } ++ ret; q.swap(q1); } return -1; } int main() { // CストリームとC++ストリームの同期を解除 // 両方のストリームを使う場合には使用しないこと std::ios::sync_with_stdio(false); // cinとcoutの同期を解除 // Reactive judge の問題には使用しないこと std::cin.tie(0); int w, h, n; cin >> w >> h >> n; vector s(2*h+1, string(2*w+1, '#')); for(int y=0; y > a(h, vector(w, 0)); vector > b(h, vector(w, 0)); for(int i=0; i> m >> z1; for(int j=0; j> z2; int y1 = z1 / w; int x1 = z1 % w; int y2 = z2 / w; int x2 = z2 % w; if(y1 == y2){ if(x2 < x1) swap(x1, x2); ++ a[y1][x1]; -- a[y1][x2]; } else{ if(y2 < y1) swap(y1, y2); ++ b[y1][x1]; -- b[y2][x1]; } z1 = z2; } } for(int y=0; y 0) s[2*y+1][2*x+2] = '.'; } } for(int x=0; x 0) s[2*y+2][2*x+1] = '.'; } } int ans = minDist(s, '#', 1, 1, 2 * h - 1, 2 * w - 1); if(ans == -1) cout << "Odekakedekinai.." << endl; else cout << (ans / 2) << endl; return 0; }