#include #include #include #include #include #include using namespace std; int arr[202][202]; int visited[202][202]; int n,starts[2],dest[2]; pair curr; string directions[] = {"UL", "UR", "R", "LR", "LL", "L"}; int xdir[] = {-2, -2, 0, 2, 2, 0}; int ydir[] = {-1, 1, 2, 1, -1, -2}; int parents[202][202][3]; void init() { for(int i = 0;i < 202;i++) { for(int j = 0;j < 202;j++) { arr[i][j] = 0; visited[i][j] = -1; } } } bool valid(int i,int j) { if(i < 0 || i >= n) { return false; } if(j < 0 || j >= n) { return false; } if(visited[i][j] >= 0) { return false; } return true; } void solve() { curr.first = starts[0]; curr.second = starts[1]; parents[curr.first][curr.second][0] = -1; parents[curr.first][curr.second][1] = -1; parents[curr.first][curr.second][2] = 0; visited[curr.first][curr.second] = 9; parents[dest[0]][dest[1]][0] = -1; parents[dest[0]][dest[1]][1] = -1; parents[dest[0]][dest[1]][2] = -1; queue< pair > q; q.push(curr); pair parent; while(q.size() > 0) { parent = q.front(); q.pop(); if(parent.first == dest[0] && parent.second == dest[1]) { return; } for(int i = 0;i < 6;i++) { if(valid(parent.first+xdir[i], parent.second+ydir[i])) { q.push(make_pair(parent.first+xdir[i], parent.second+ydir[i])); parents[parent.first+xdir[i]][parent.second+ydir[i]][0] = parent.first; parents[parent.first+xdir[i]][parent.second+ydir[i]][1] = parent.second; parents[parent.first+xdir[i]][parent.second+ydir[i]][2] = parents[parent.first][parent.second][2] + 1; visited[parent.first+xdir[i]][parent.second+ydir[i]] = i; } } } } void printShortestPath(int i,int j) { if(i == starts[0] && j == starts[1]) { return; } printShortestPath(parents[i][j][0], parents[i][j][1]); cout<> n; cin >> starts[0] >> starts[1] >> dest[0] >> dest[1]; init(); solve(); if(parents[dest[0]][dest[1]][2] == -1) { cout << "Impossible\n"; } else { cout<