#include #include #include #include using namespace std; #define CENTER 32 #define BIT_W 6 #define PAD (1< snake_t; vector rocks; #define WAYS 6 //int wx[] = {1,1,0,0,-1,-1}; //int wy[] = {0,-1,1,-1,0,1}; int way[] = { PAD, PAD-1, 1,-1, -PAD, -PAD+1 }; bool connect(point_t p1,point_t p2){ int diff = p1-p2; for(int i=0;i &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, int> &dists, snake_t &snake){ map, int>::iterator p; p = dists.find(make_pair(snake[0],snake[1])); if(p == dists.end()) return MAX_TURN*2; return p->second; } int main(void){ while(true){ int n; cin >> n; if(n==0) break; // read snake vector > p_snake; p_snake.resize(n); for(int i=0;i> p_snake[i].first >> p_snake[i].second; // read rock int rock_size; cin >> rock_size; vector > p_rocks; p_rocks.resize(rock_size); for(int i=0;i> p_rocks[i].first >> p_rocks[i].second; // read goal pair p_goal; cin >> p_goal.first >> p_goal.second; // remove no-meaning rocks vector > rocks_tmp = p_rocks; rocks.clear(); for(int i=0;i<(int)rocks_tmp.size();i++){ if(abs(p_goal.first - rocks_tmp[i].first )>(MAX_TURN+MAX_SNAKE_LEN)|| abs(p_goal.second - rocks_tmp[i].second)>(MAX_TURN+MAX_SNAKE_LEN)) continue; p_rocks.push_back(rocks_tmp[i]); } // shift_goal to (CENTER,CENTER) for(int i=0;i<(int)p_snake.size();i++){ p_snake[i].first = p_snake[i].first - p_goal.first + CENTER; p_snake[i].second = p_snake[i].second - p_goal.second + CENTER; } for(int i=0;i<(int)p_rocks.size();i++){ p_rocks[i].first = p_rocks[i].first - p_goal.first + CENTER; p_rocks[i].second = p_rocks[i].second - p_goal.second + CENTER; } // make snake, rocks point_t goal = CENTER*PAD + CENTER; snake_t snake; for(int i=0;i<(int)p_snake.size();i++) snake.push_back(p_snake[i].first * PAD + p_snake[i].second); rocks.clear(); for(int i=0;i<(int)p_rocks.size();i++) rocks.push_back(p_rocks[i].first * PAD + p_rocks[i].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::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 == MAX_TURN) 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) > MAX_TURN) 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; }