#include using namespace std; int boardNode[205][205]; pair PossibleMoves[6]; vector edgeList[100000]; pair nodeToGrid[100000]; vector lastVis[100000]; int minDistance[100000]; int n; string priorty[6] = {"UL","UR","R","LR","LL","L"}; bool isInGrid(int x,int y) { return (x >= 0 && x < n && y >= 0 && y < n); } string typeOfMove(int x,int y,int nextX,int nextY) { if(x == nextX) if(y < nextY) return "L"; else return "R"; else if(x < nextX) if(y < nextY) return "UL"; else return "UR"; else if(y < nextY) return "LL"; else return "LR"; } int searchToFind(vector >& toFindIn,string toFind) { for(int i = 0;i < toFindIn.size();i++) { if(toFindIn[i].first == toFind) return i; } return -1; } int main() { reverse(priorty,priorty + 6); PossibleMoves[0] = {-2,-1}; PossibleMoves[1] = {-2,1}; PossibleMoves[2] = {0,2}; PossibleMoves[3] = {0,-2}; PossibleMoves[4] = {2,-1}; PossibleMoves[5] = {2,1}; cin >> n; int startX,startY,endX,endY; cin >> startX >> startY >> endX >> endY; int curNode = 0; for(int i = 0;i < n;i++) { for(int j = 0;j < n;j++) boardNode[i][j] = curNode,nodeToGrid[curNode] = make_pair(i,j),curNode++; } for(int i = 0;i < n;i++) { for(int j = 0;j < n;j++) { for(int k = 0;k < 6;k++) { int newX = i + PossibleMoves[k].first; int newY = j + PossibleMoves[k].second; if(isInGrid(newX,newY)) edgeList[boardNode[i][j]].push_back(boardNode[newX][newY]); } } } for(int i = 0;i < 42025;i++) minDistance[i] = 1e8; minDistance[boardNode[startX][startY]] = 0; priority_queue myQ; myQ.push(boardNode[startX][startY]); while(!myQ.empty()) { int topEle = myQ.top(); myQ.pop(); for(int i = 0;i < edgeList[topEle].size();i++) { int curEle = edgeList[topEle][i]; if(minDistance[topEle] + 1 < minDistance[curEle]) { minDistance[curEle] = minDistance[topEle] + 1; myQ.push(curEle); lastVis[curEle].clear(); lastVis[curEle].push_back(topEle); } else if(minDistance[topEle] + 1 == minDistance[curEle]) lastVis[curEle].push_back(topEle); } } if(minDistance[boardNode[endX][endY]] == 1e8) { cout << "Impossible"; return 0; } cout << minDistance[boardNode[endX][endY]] << endl; int x = endX; int y = endY; vector way; while(x != startX || y != startY) { vector > PossMoves; for(int i = 0;i < lastVis[boardNode[x][y]].size();i++) { int elementHash = lastVis[boardNode[x][y]][i]; PossMoves.push_back(make_pair(typeOfMove(x,y,nodeToGrid[elementHash].first,nodeToGrid[elementHash].second),elementHash)); } for(int i = 0;i < 6;i++) { int idx = searchToFind(PossMoves,priorty[i]); if(idx == -1) continue; way.push_back(PossMoves[idx].first); x = nodeToGrid[PossMoves[idx].second].first; y = nodeToGrid[PossMoves[idx].second].second; break; } } reverse(way.begin(),way.end()); for(int i = 0;i < way.size();i++) cout << way[i] << " "; }