#include using namespace std; bool isValid(int i, int j, int n) { return (i >= 0 && i < n && j >= 0 && j < n ); } vector, string> > getNextMovements(pair cur, int n) { vector, string> > movs; if (isValid(cur.first - 2, cur.second - 1, n) ) { // UL movs.push_back(make_pair(make_pair(cur.first - 2, cur.second - 1), "UL")); } if (isValid(cur.first - 2, cur.second + 1, n) ) { //UR movs.push_back(make_pair(make_pair(cur.first - 2, cur.second + 1), "UR")); } if (isValid(cur.first, cur.second + 2, n) ) { //R movs.push_back(make_pair(make_pair(cur.first, cur.second + 2), "R")); } if (isValid(cur.first + 2, cur.second + 1, n) ) { //LR movs.push_back(make_pair(make_pair(cur.first + 2, cur.second + 1), "LR")); } if (isValid(cur.first + 2, cur.second - 1, n) ) { //LL movs.push_back(make_pair(make_pair(cur.first + 2, cur.second - 1), "LL")); } if (isValid(cur.first, cur.second - 2, n) ) { //L movs.push_back(make_pair(make_pair(cur.first, cur.second - 2), "L")); } return movs; } 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. // priority UL, UR, R, LR, LL, L. pair s_pos = make_pair(i_start, j_start); pair e_pos = make_pair(i_end, j_end); vector > distance(n, vector(n, -1)); vector > > fromNode(n, vector>(n)); vector > command(n, vector(n, "")); queue > nextPosition; distance[s_pos.first][s_pos.second] = 0; fromNode[s_pos.first][s_pos.second] = s_pos; nextPosition.push(s_pos); while(!nextPosition.empty()) { pair cur_pos = nextPosition.front(); //cerr << "Visiting node " << cur_pos.first << ", " << cur_pos.second << endl; nextPosition.pop(); if (cur_pos == e_pos) { break; } for (auto next_moves_and_command : getNextMovements(cur_pos, n)) { pair next_moves = next_moves_and_command.first; string cmd = next_moves_and_command.second; if (distance[next_moves.first][next_moves.second] == -1) { nextPosition.push(next_moves); //cerr << "Queueing node " << next_moves.first << ", " << next_moves.second << " with cmd " << cmd << endl; command[next_moves.first][next_moves.second] = cmd; fromNode[next_moves.first][next_moves.second] = cur_pos; distance[next_moves.first][next_moves.second] = distance[cur_pos.first][cur_pos.second] + 1; } } } if (distance[e_pos.first][e_pos.second] == -1) { cout << "Impossible" << endl; } else { cout << distance[e_pos.first][e_pos.second] << endl; pair cur_pos = e_pos; //fromNode[e_pos.first][e_pos.second]; stack reverse_cmd; while (cur_pos != s_pos) { //cerr << cur_pos.first << ", " << cur_pos.second << "-> "; reverse_cmd.push(command[cur_pos.first][cur_pos.second]); cur_pos = fromNode[cur_pos.first][cur_pos.second]; } while (!reverse_cmd.empty()) { cout << reverse_cmd.top() << " "; reverse_cmd.pop(); } 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; }