#include using namespace std; #define N 205 pair < int , pair < int , int > > camefrom[N][N]; bool vis[N][N]; int dist[N][N]; int dy[] = {-1 , 1 , 2 , 1 , -1 , -2}; int dx[] = {-2 , -2 , 0 , 2 , 2 , 0}; string paths[] = {"UL", "UR", "R", "LR", "LL", "L"}; int n , si , sj , di , dj; #define INF 0x3f3f3f3f #define pii pair < int , pair < int , pair < int , int > > > struct cmp { bool operator()(const pii &aa,const pii &bb) { if(aa.first == bb.first) { return aa.second.first > bb.second.first; } return aa.first > bb.first; } }; int Dijkstra() { memset(vis , 0 , sizeof(vis)); memset(dist , INF , sizeof(dist)); priority_queue < pii , vector < pii > , cmp > pq; pq.push({0 , {INF, {si , sj}}}); dist[si][sj] = 0; pii tmp; int ci , cj; while(!pq.empty()) { tmp = pq.top(); pq.pop(); ci = tmp.second.second.first; cj = tmp.second.second.second; if(ci == di && cj == dj) return tmp.first; if(vis[ci][cj]) continue; for(int i = 0;i < 6;i++) { if(ci + dx[i] < 0 || ci + dx[i] >= n || cj + dy[i] < 0 || cj + dy[i] >= n) continue; if(dist[ci + dx[i]][cj + dy[i]] > dist[ci][cj] + 1) { camefrom[ci + dx[i]][cj + dy[i]] = {i , {ci , cj}}; dist[ci + dx[i]][cj + dy[i]] = dist[ci][cj] + 1; pq.push({dist[ci + dx[i]][cj + dy[i]] , {i , {ci + dx[i] , cj + dy[i]}}}); } } } return -1; } void PrintPath() { int ci = di , cj = dj , cii , cjj; vector < int > vi; while(ci != si || cj != sj) { vi.push_back(camefrom[ci][cj].first); cii = camefrom[ci][cj].second.first; cjj = camefrom[ci][cj].second.second; ci = cii; cj = cjj; } reverse(vi.begin() , vi.end()); for(int i=0;i> n; cin >> si >> sj >> di >> dj; int ans = Dijkstra(); if(ans == -1) { cout << "Impossible" << endl; } else { cout << ans << endl; PrintPath(); } return 0; }