#include using namespace std; string trim(const string& str) { size_t first = str.find_first_not_of(' '); if (string::npos == first) { return str; } size_t last = str.find_last_not_of(' '); return str.substr(first, (last - first + 1)); } struct QEntry { int i, j, dist; string path; }; 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. vector> visited(n, vector(n, false)); map, QEntry> parents; //set> visited; queue q; if (i_start == i_end && j_start == j_end) { cout << "0" << endl; return; } QEntry qe; q.push({ i_start, j_start, 0, "" }); visited[i_start][j_start] = true; while (!q.empty()) { qe = q.front(); q.pop(); if (qe.i == i_end && qe.j == j_end) break; //UR if ((qe.i - 2) >= 0 && (qe.j + 1)= 0 && (qe.j - 1) >= 0 && !visited[qe.i - 2][qe.j - 1]) { parents[make_pair((qe.i - 2), (qe.j - 1))] = qe; visited[(qe.i - 2)][(qe.j - 1)] = true; q.push({ (qe.i - 2), (qe.j - 1), qe.dist + 1, "UL " }); } //R if ((qe.j + 2)= 0 && !visited[qe.i][qe.j - 2]) { parents[make_pair(qe.i, (qe.j - 2))] = qe; visited[qe.i][(qe.j - 2)] = true; q.push({ qe.i, (qe.j - 2), qe.dist + 1, "L " }); } //LR if ((qe.i + 2)= 0 && !visited[qe.i + 2][qe.j - 1]) { parents[make_pair((qe.i + 2), (qe.j - 1))] = qe; visited[(qe.i + 2)][(qe.j - 1)] = true; q.push({ (qe.i + 2), (qe.j - 1), qe.dist + 1,"LL " }); } } if (!visited[i_end][j_end])//find in visited { cout << "Impossible" << endl; } else { cout << qe.dist << endl; int i = qe.i, j = qe.j; vector op; op.push_back(qe.path); while (1) { map, QEntry>::iterator it = parents.find(make_pair(i, j)); if (it != parents.end()) { QEntry par = it->second; op.push_back(par.path); i = par.i, j = par.j; if (i == i_start && j == j_start) break; } else break; } for(vector::reverse_iterator it=op.rbegin(); it!=op.rend();++it) cout<<*it; 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; }