#include using namespace std; int g_n; bool matrix[200][200]; int moves[6][2] = { { -2,-1 } ,{ -2,1 } ,{0,2},{2,1},{2,-1},{ 0,-2 } }; string movesNames[6] = { "UL","UR", "R" , "LR", "LL" ,"L" }; vector g_seq; void getShortestPath(int i_start, int j_start, int i_end, int j_end, vector seq) { if (g_seq.size() > 0 && seq.size() >= g_seq.size()) return; for (int i = 0; i < 6; i++) { int newIPos = i_start + moves[i][0]; int newJPos = j_start + moves[i][1]; if (newIPos < 0 || newIPos >= g_n || newJPos < 0 || newJPos >= g_n || matrix[newIPos][newJPos] == true) //visited continue; matrix[newIPos][newJPos] = true; //visited seq.push_back(movesNames[i]); if (newIPos == i_end && newJPos == j_end) { if (g_seq.size() == 0 || seq.size() < g_seq.size()) { g_seq = seq; } } else { getShortestPath(newIPos, newJPos, i_end, j_end, seq); } seq.pop_back(); matrix[newIPos][newJPos] = false; } } void printShortestPath(int n, int i_start, int j_start, int i_end, int j_end) { // Print the distance along with the sequence of moves. g_n = n; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { matrix[i][j] = false; } } vector seq; matrix[i_start][j_start] = true; getShortestPath(i_start, j_start, i_end, j_end, seq); if (g_seq.size() == 0) { cout << "Impossible" << endl; } else { cout << g_seq.size()<< endl; for (int i = 0; i < g_seq.size(); i++) { cout << g_seq[i] << " "; } cout << endl; } } int main() { int n; cin >> 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; }