#include #include #include #include using namespace std; typedef vector< pair > snake_t; typedef pair rock_t; int dx[6] = {0, 1, 1, 0, -1, -1}; int dy[6] = {-1, -1, 0, 1, 1, 0}; void rec(snake_t &snake, int pos, bool ismoved, const set &rocks, set &newstate, set &whole) { if (pos >= snake.size()) { if (whole.find(snake) == whole.end()) { whole.insert(snake); newstate.insert(snake); } return; } set forbidden; forbidden = rocks; for (int j = 0; j < pos-1; j++) { forbidden.insert(make_pair(snake[j].first, snake[j].second)); for (int i = 0; i < 6; i++) { forbidden.insert(make_pair(snake[j].first + dx[i], snake[j].second + dy[i])); } } set available, available1; if (pos == 0) { for (int i = 0; i < 6; i++) { available.insert(make_pair(snake[1].first + dx[i], snake[1].second + dy[i])); } } else if (pos == snake.size() - 1) { for (int i = 0; i < 6; i++) { available.insert(make_pair(snake[snake.size()-2].first + dx[i], snake[snake.size()-2].second + dy[i])); } } else { for (int i = 0; i < 6; i++) { available1.insert(make_pair(snake[pos-1].first + dx[i], snake[pos-1].second + dy[i])); } for (int i = 0; i < 6; i++) { pair target = make_pair(snake[pos+1].first + dx[i], snake[pos+1].second + dy[i]); if (available1.find(target) != available1.end()) { available.insert(target); } } } pair original = snake[pos]; if (!ismoved) { for (int i = 0; i < 6; i++) { pair moved = make_pair(original.first + dx[i], original.second + dy[i]); if (forbidden.find(moved) == forbidden.end() && available.find(moved) != available.end()) { snake[pos] = moved; rec(snake, pos+1, true, rocks, newstate, whole); snake[pos] = original; } } } if (forbidden.find(snake[pos]) == forbidden.end() && available.find(snake[pos]) != available.end()) { rec(snake, pos+1, false, rocks, newstate, whole); } } int main() { while (true) { int n; snake_t initial; cin >> n; if (n == 0) { break; } for (int i = 0; i < n; i++) { int x, y; cin >> x >> y; initial.push_back(make_pair(x, y)); } int k; set rocks; cin >> k; for (int i = 0; i < k; i++) { int x, y; cin >> x >> y; rocks.insert(make_pair(x, y)); } int X, Y; cin >> X >> Y; set whole; set state[2]; int cur = 0, nxt = 1; state[cur].insert(initial); whole.insert(initial); for (int step = 1; step <= 20; step++) { for (set::iterator p = state[cur].begin(); p != state[cur].end(); p++) { snake_t tmp = *p; rec(tmp, 0, false, rocks, state[nxt], whole); } for (set::iterator p = state[nxt].begin(); p != state[nxt].end(); p++) { if ((*p)[0].first == X && (*p)[0].second == Y) { cout << step << endl; goto quit; } } cur ^= 1; nxt ^= 1; state[nxt].clear(); } quit: ; } }