#include using namespace std; int N; //details all 6 possible movements int row[] = { 2, 0, -2, 2, 0, -2}; int col[] = { -1, -2, -1, 1, 2, 1}; // Check if (x, y) is valid chess board cordinates bool valid(int x, int y) { if (x < 0 || y < 0 || x >= N || y >= N) return false; return true; } // queue node used in BFS struct Node { int x, y, dist; bool const operator==(const Node& o) const { return x == o.x && y == o.y; } bool operator<(const Node& o) const { return x < o.x || (x == o.x && y < o.y); } }; // Find minimum number of steps taken by the knight // from source to reach destination using BFS int BFS(Node src, Node dest) { // map to check if matrix cell is visited before or not map visited; // create a queue and enqueue first node queue q; q.push(src); // run till queue is not empty while (!q.empty()) { // pop front node from queue and process it Node node = q.front(); q.pop(); int x = node.x; int y = node.y; int dist = node.dist; // if destination is reached, return distance if (x == dest.x && y == dest.y) return dist; // Skip if location is visited before if (!visited.count(node)) { // mark current node as visited visited[node] = true; // check for all 8 possible movements for a knight // and enqueue each valid movement into the queue for (int i = 0; i < 6; ++i) { // Get the new valid position of Knight from current // position on chessboard and enqueue it in the // queue with +1 distance int x1 = x + row[i]; int y1 = y + col[i]; if (valid(x1, y1)) q.push({x1, y1, dist + 1}); } } } // return INFINITY if path is not possible return 0; } // main function int main() { cin >> N; int x_src, y_src, x_dest, y_dest; cin >> x_src >> y_src; Node src = { x_src, y_src}; cin >> x_dest >> y_dest; // destination coordinates Node dest = {x_dest, y_dest}; int dis = BFS(src, dest); if(dis) cout << dis << endl; else cout << "Impossible"; return 0; }