#include using namespace std; void printShortestPath(int n, int i_start, int j_start, int i_end, int j_end) { pair beg(i_start,j_start); pair end(i_end,j_end); queue< pair > q; int i, mark[n][n], dist[n][n]; string moves[n][n]; pair par[n][n]; for(i=0; i cur = q.front(); q.pop(); //cout< ms; while(1){ ms.push_back( moves[cur.first][cur.second] ); if(beg == par[cur.first][cur.second]){ break; } cur = par[cur.first][cur.second]; } reverse(ms.begin(), ms.end()); for(int i=0; i= 0 && cur.second-1 >= 0 && mark[cur.first-2][cur.second-1] == 0){ q.push(make_pair(cur.first-2,cur.second-1)); mark[cur.first-2][cur.second-1] = 1; dist[cur.first-2][cur.second-1] = dist[cur.first][cur.second] + 1; par[cur.first-2][cur.second-1] = cur; moves[cur.first-2][cur.second-1] = "UL"; } if(cur.first-2 >= 0 && cur.second+1 < n && mark[cur.first-2][cur.second+1] == 0){ q.push(make_pair(cur.first-2,cur.second+1)); mark[cur.first-2][cur.second+1] = 1; dist[cur.first-2][cur.second+1] = dist[cur.first][cur.second] + 1; par[cur.first-2][cur.second+1] = cur; moves[cur.first-2][cur.second+1] = "UR"; } if(cur.second+2 < n && mark[cur.first][cur.second+2] == 0){ q.push(make_pair(cur.first,cur.second+2)); mark[cur.first][cur.second+2] = 1; dist[cur.first][cur.second+2] = dist[cur.first][cur.second] + 1; par[cur.first][cur.second+2] = cur; moves[cur.first][cur.second+2] = "R"; } if(cur.first+2 < n && cur.second+1 < n && mark[cur.first+2][cur.second+1] == 0){ q.push(make_pair(cur.first+2,cur.second+1)); mark[cur.first+2][cur.second+1] = 1; dist[cur.first+2][cur.second+1] = dist[cur.first][cur.second] + 1; par[cur.first+2][cur.second+1] = cur; moves[cur.first+2][cur.second+1] = "LR"; } if(cur.first+2 < n && cur.second-1 >= 0 && mark[cur.first+2][cur.second-1] == 0){ q.push(make_pair(cur.first+2,cur.second-1)); mark[cur.first+2][cur.second-1] = 1; dist[cur.first+2][cur.second-1] = dist[cur.first][cur.second] + 1; par[cur.first+2][cur.second-1] = cur; moves[cur.first+2][cur.second-1] = "LL"; } if(cur.second-2 >= 0 && mark[cur.first][cur.second-2] == 0){ q.push(make_pair(cur.first,cur.second-2)); mark[cur.first][cur.second-2] = 1; dist[cur.first][cur.second-2] = dist[cur.first][cur.second] + 1; par[cur.first][cur.second-2] = cur; moves[cur.first][cur.second-2] = "L"; } } cout<<"Impossible"; } 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; }