#include #include #include #include using namespace std; typedef pair iPair; void print_ans(const vector > &prev, int i_start, int j_start, int i_end, int j_end){ int count = 0; vector moves; int i = i_end, j = j_end; while(i != i_start || j != j_start){ iPair p = prev[i][j]; int row_diff = p.first - i; int col_diff = p.second - j; if(row_diff == -2 && col_diff == -1) moves.push_back("LR"); else if(row_diff == -2 && col_diff == 1) moves.push_back("LL"); else if(row_diff == 0 && col_diff == -2) moves.push_back("R"); else if(row_diff == 2 && col_diff == 1) moves.push_back("UL"); else if(row_diff == 2 && col_diff == -1) moves.push_back("UR"); else if(row_diff == 0 && col_diff == 2) moves.push_back("L"); i = p.first; j = p.second; count++; } cout << count << endl; for(int i = moves.size()-1; i >= 0; i--){ cout << moves[i] << " "; } cout << endl; } void printShortestPath(int n, int i_start, int j_start, int i_end, int j_end) { vector > prev(n, vector(n)); queue q; set s; q.push(make_pair(i_start, j_start)); while(!q.empty()){ iPair curr = q.front(); q.pop(); //s.insert(curr); if(curr.first == i_end && curr.second == j_end){ print_ans(prev, i_start, j_start, i_end, j_end); return; } bool one_left = (curr.second - 1 >= 0); bool two_left = (curr.second - 2 >= 0); bool one_right = (curr.second + 1 < n); bool two_right = (curr.second + 2 < n); bool two_up = (curr.first - 2 >= 0); bool two_down = (curr.first + 2 < n); if(one_left && two_up){ iPair next = make_pair(curr.first - 2, curr.second - 1); if(s.find(next) == s.end()){ s.insert(next); q.push(next); if(prev[next.first][next.second] == make_pair(0,0)) prev[next.first][next.second] = curr; } } if(one_right && two_up){ iPair next = make_pair(curr.first - 2, curr.second + 1); if(s.find(next) == s.end()){ s.insert(next); q.push(next); if(prev[next.first][next.second] == make_pair(0,0)) prev[next.first][next.second] = curr; } } if(two_right){ iPair next = make_pair(curr.first, curr.second + 2); if(s.find(next) == s.end()){ s.insert(next); q.push(next); if(prev[next.first][next.second] == make_pair(0,0)) prev[next.first][next.second] = curr; } } if(one_right && two_down){ iPair next = make_pair(curr.first + 2, curr.second + 1); if(s.find(next) == s.end()){ s.insert(next); q.push(next); if(prev[next.first][next.second] == make_pair(0,0)) prev[next.first][next.second] = curr; } } if(one_left && two_down){ iPair next = make_pair(curr.first + 2, curr.second - 1); if(s.find(next) == s.end()){ s.insert(next); q.push(next); if(prev[next.first][next.second] == make_pair(0,0)) prev[next.first][next.second] = curr; } } if(two_left){ iPair next = make_pair(curr.first, curr.second - 2); if(s.find(next) == s.end()){ s.insert(next); q.push(next); if(prev[next.first][next.second] == make_pair(0,0)) prev[next.first][next.second] = curr; } } } cout << "Impossible" << 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; }