#include #define fst first #define snd second #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define clr(a, v) memset( a , v , sizeof(a) ) #define pb push_back #define mp make_pair #define sz size() #define FORN( i , s , n ) for( int i = (s) ; i < (n) ; i++ ) #define FOR( i , n ) FORN( i , 0 , n ) #define FORIT( i , x ) for( typeof x.begin() i = x.begin() ; i != x.end() ; i++ ) #define trace(x) cout << #x << ": " << x << endl; #define trace2(x, y) cout << #x << ": " << x << " | " << #y << ": " << y << endl; #define trace3(x, y, z) cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl; #define read ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); using namespace std; typedef long long int64; typedef vector vi; typedef pair ii; typedef vector vs; typedef vector vii; int n; int dis[205][205]; ii pre[205][205]; string pre_s[205][205]; int dx [6] = {-2,-2,0,2,2,0}; int dy [6] = {-1,1,2,1,-1,-2}; string s[6] = {"UL", "UR", "R", "LR", "LL", "L"}; bool valid(int x, int y) { if( min(x,y) < 0 or max(x,y) >= n) return 0; return 1; } 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. FOR(i, n) FOR(j,n) dis[i][j] = -1; queue Q; Q.push( ii( i_start, j_start ) ); dis[i_start][j_start] = 0; while(!Q.empty()) { ii nxt = Q.front(); Q.pop(); //trace3(nxt.fst, nxt.snd, dis[nxt.fst][nxt.snd]); FOR(k,6) { int nx = nxt.fst + dx[k]; int ny = nxt.snd + dy[k]; if (valid(nx,ny) and dis[nx][ny] == -1 ) { dis[nx][ny] = dis[nxt.fst][nxt.snd] + 1; pre_s[nx][ny] = s[k]; pre[nx][ny] = nxt; Q.push( ii(nx,ny) ); } } } if ( dis[i_end][j_end] == -1 ) { puts("Impossible"); return; } cout<> 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; }