#include #include #include #include #include using namespace std; typedef pair ii; typedef pair iis; int n,res; bool a[202][202]; ii s,e; iis dir[6]; vector result; void init() { //UL, UR, R, LR, LL, L dir[0].first = make_pair(-2,-1); dir[0].second = "UL"; dir[1].first = make_pair(-2,1); dir[1].second = "UR"; dir[2].first = make_pair(0,2); dir[2].second = "R"; dir[3].first = make_pair(2,1); dir[3].second = "LR"; dir[4].first = make_pair(2,-1); dir[4].second = "LL"; dir[5].first = make_pair(0,-2); dir[5].second = "L"; } bool check_move(ii &cur,ii &next) { if (cur.first + next.first > n) return 0; if (cur.second + next.second > n) return 0; if (cur.first + next.first < 1) return 0; if (cur.second + next.second < 1) return 0; int tmp = cur.first + next.first + cur.second+ next.second; if (abs(tmp-e.first-e.second) > abs(cur.first + cur.second - e.first - e.second)) return 0; if (a[cur.first + next.first][cur.second + next.second] == 1) return 0; return 1; } void dfs(ii cur, iis &next, int &count, vector& tmp_res) { count++; //cout << cur.first << " " << cur.second << endl; tmp_res.push_back(next.second); cur.first += next.first.first; cur.second += next.first.second; a[cur.first][cur.second] = 1; if (cur != e) { for (int i=0;i<=5;i++) { if (check_move(cur,dir[i].first)) dfs(cur,dir[i],count,tmp_res); } } if (tmp_res.size() < res and cur == e) { result = tmp_res; res = result.size(); } tmp_res.pop_back(); a[cur.first][cur.second] = 0; } void solve() { init(); for (int i=0;i<=5;i++) { ii cur = s; if (check_move(cur,dir[i].first)) { vector tmp_res; int count = 0; dfs(cur,dir[i],count,tmp_res); } } if (res == 999999) { cout << "Impossible"; } else { cout << res << endl; for (int i=0;i> n; n++; int x,y,z,t; cin >> x >> y >> z >> t; s.first = x+1; s.second = y+1; e.first = z+1; e.second = t+1; res = 999999; solve(); return 0; }