#include #include #include #include using namespace std; typedef vector > snake_t; typedef unsigned long long hash_t; int dx[] = {0 , 1, 1, 0,-1,-1}; int dy[] = {-1,-1, 0, 1, 1, 0}; inline int min_dist(const pair& p1,const pair& p2){ int dx = p1.first - p2.first; int dy = p1.second - p2.second; return (dx*dy>=0) abs(dx)+abs(dy) : max(abs(dx),abs(dx)); } struct state_t { snake_t snake; int turn; int priority; state_t(snake_t _snake,int _turn,const pair& goal) : snake(_snake),turn(_turn) { int lower = min_dist(snake[0],goal) + (min_dist(snake[1],goal) - 1); priority = - turn - lower; } }; void show(const snake_t& snake){ cout << "----" << endl; for(int i=0;i >& rocks, vector& next_set,bool movable){ if(idx >= snake.size()){ next_set.push_back(snake); return; } if(!death(snake,idx)) gen(snake,idx+1,rocks,next_set,true); if(movable){ for(int i=0;i<6;i++){ snake_t next_snake = snake; next_snake[idx].first = snake[idx].first + dx[i]; next_snake[idx].second = snake[idx].second + dy[i]; if(idx < snake.size()-1 && min_dist(next_snake[idx],next_snake[idx+1]) != 1) continue; if(idx > 0 && min_dist(next_snake[idx],next_snake[idx-1]) != 1) continue; if(rocks.find(next_snake[idx]) != rocks.end()) continue; if(!death(next_snake,idx)) gen(next_snake,idx+1,rocks,next_set,false); } } } bool operator<(const state_t& st1,const state_t& st2){ return st1.priority < st2.priority; } int main(){ int N; while(cin>>N,N){ snake_t start(N); int st_x,st_y; cin >> st_x >> st_y; start[0].first = start[0].second = 0; for(int i=1;i> x >> y; start[i].first = x-st_x; start[i].second = y-st_y; } int K; cin >> K; set > rocks; for(int i=0;i> x >> y; rocks.insert(make_pair(x-st_x,y-st_y)); } pair goal; cin >> goal.first >> goal.second; goal.first -= st_x; goal.second -= st_y; set done; priority_queue que; que.push(state_t(start,0,goal)); while(!que.empty()){ state_t state = que.top(); que.pop(); hash_t h = hash_of(state.snake); // cout << h.first << " " << h.second << endl; if(done.find(h) == done.end()){ done.insert(h); snake_t& snake = state.snake; int turn = state.turn; if(snake[0] == goal){ cout << turn << endl; break; }else if(turn > 20){ cout << "Impossible" << endl;//(error) break; } vector next_set; gen(snake,0,rocks,next_set,true); for(int i=0;i