#include using namespace std; #define ROW 200 #define COL 200 bool visited[ROW][COL]; //to store matrix cell cordinates struct Point { int x; int y; }; // An Data Structure for queue used in BFS struct queueNode { Point pt; // The cordinates of a cell int dist; // cell's distance of from the source vector path; }; // check whether given cell (row, col) is a valid // cell or not. bool isValid(int row, int col, int N) { // return true if row number and column number // is in range return (row >= 0) && (row < N) && (col >= 0) && (col < N); } // These arrays are used to get row and column // numbers of 4 neighbours of a given cell int rowNum[] = {-2, -2, 0, 2, 2, 0}; int colNum[] = {-1, 1, 2, 1, -1, -2}; string dir[6] = {"UL","UR","R","LR","LL","L"}; // function to find the shortest path between // a given source cell to a destination cell. int BFS(Point src, Point dest, int N, vector& sPath) { vector path; path.push_back(""); // Mark the source cell as visited visited[src.x][src.y] = true; // Create a queue for BFS queue q; // distance of source cell is 0 queueNode s = {src, 0, path}; q.push(s); // Enqueue source cell // Do a BFS starting from source cell while (!q.empty()) { queueNode curr = q.front(); path = curr.path; Point pt = curr.pt; // If we have reached the destination cell, // we are done if (pt.x == dest.x && pt.y == dest.y) { sPath = path; return curr.dist; } // Otherwise dequeue the front cell in the queue // and enqueue its adjacent cells q.pop(); for (int i = 0; i < 6; i++) { int row = pt.x + rowNum[i]; int col = pt.y + colNum[i]; // if adjacent cell is valid, has path and // not visited yet, enqueue it. if (isValid(row, col, N) && !visited[row][col]) { path.push_back(dir[i]); // mark cell as visited and enqueue it visited[row][col] = true; queueNode Adjcell = { {row, col}, curr.dist + 1, path }; q.push(Adjcell); path.pop_back(); } } } return -1; } void printShortestPath(int n, int i_start, int j_start, int i_end, int j_end) { memset(visited, false, n); vector sPath; Point src, dest; src.x = i_start; src.y = j_start; dest.x = i_end; dest.y = j_end; int ans = BFS(src,dest,n, sPath); if(ans == -1) cout << "Impossible" << endl; else { cout << ans << endl; for(int i=1;i> n; int i_start; int j_start; int i_end; int j_end; cin >> i_start >> j_start >> i_end >> j_end; printShortestPath(n, i_start, j_start, i_end, j_end); return 0; }