#include #include #include #include using namespace std; typedef pair point_t; typedef vector snake_t; vector rocks; int rock_size; int wx[] = {1,1,0,0,-1,-1}; int wy[] = {0,-1,1,-1,0,1}; bool connect(const point_t &p1,const point_t &p2){ int dx = p1.first - p2.first; int dy = p1.second - p2.second; for(int i=0;i<6;i++){ if(dx == wx[i] && dy == wy[i]) return true; } return false; } bool kabenonakaniiru(const point_t &p){ for(int j=0;j &found_set,set &next_set){ if(idx >= n){ if(found_set.find(snake) == found_set.end()){ found_set.insert(snake); next_set.insert(snake); } return; } for(int i=0;i<6;i++){ pair np; np.first = snake[idx].first + wx[i]; np.second = snake[idx].second + wy[i]; if(idx != 0 && !connect(np,snake[idx-1])) continue; if(idx != n-1 && !connect(np,snake[idx+1])) continue; if(kabenonakaniiru(np)) continue; if(lost_simasita(snake, np, idx)) continue; pair backup = snake[idx]; snake[idx] = np; next(snake, idx+2, n, found_set, next_set); snake[idx] = backup; } // dont move; pair np = snake[idx]; if(!lost_simasita(snake, np, idx)) next(snake, idx+1, n, found_set, next_set); } int dist(map, int> &dists, snake_t &snake){ map, int>::iterator p; p = dists.find(make_pair(snake[0],snake[1])); if(p == dists.end()) return 99; return p->second; } int main(void){ while(true){ snake_t snake; int n; cin >> n; if(n==0) break; // read snake snake.resize(n); for(int i=0;i> snake[i].first >> snake[i].second; // read rock cin >> rock_size; rocks.resize(rock_size); for(int i=0;i> rocks[i].first >> rocks[i].second; // read goal point_t goal; cin >> goal.first >> goal.second; // ready dist_map of snake map, int> dists; set found_set, next_set, current_set; snake_t snake2; snake2.resize(2); snake2[0] = goal; for(int i=0;i<6;i++){ snake2[1].first = goal.first + wx[i]; snake2[1].second = goal.second + wy[i]; next_set.insert(snake2); found_set.insert(snake2); dists.insert(make_pair(make_pair(snake2[0],snake2[1]), 0)); } for(int i=1;i<20;i++){ current_set.clear(); current_set.swap(next_set); for(set::iterator p = current_set.begin(); p!=current_set.end(); p++) next(snake2 = *p, 0, 2, found_set, next_set); for(set::iterator p = next_set.begin(); p!=next_set.end(); p++) dists.insert(make_pair(make_pair((*p)[0], (*p)[1]),i)); } found_set.clear(); found_set.insert(snake); next_set.clear(); next_set.insert(snake); int ans = 0; while(true){ ans++; if(ans == 20) break; current_set.swap(next_set); next_set.clear(); //cout << ans << " " << current_set.size() <::iterator p = current_set.begin(); p != current_set.end(); p++){ snake_t snk = *p; if(ans + dist(dists,snk) >= 21) continue; next(snk, 0, n, found_set, next_set); } bool found = false; for(set::iterator p = next_set.begin(); p != next_set.end(); p++){ if((*p)[0] == goal){ found = true; break; } } if(found) break; } cout << ans << endl; } return 0; }