#include #include #include #include #include #include #include using namespace std; typedef pair cord; void printpath(int i, int j, const vector< vector > &par, const vector< vector > &mov){ if (par[i][j].first == -1) return; printpath(par[i][j].first, par[i][j].second, par, mov); cout << mov[i][j] << " " ; } int main() { int n, xin, yin, xo, yo; cin >> n; cin >> xin >> yin >> xo >> yo; vector< vector > dis(n, vector(n, -1)); vector< vector > par(n, vector(n, make_pair(-1, -1))); vector< vector > mov(n, vector(n, "END")); queue q; q.push(make_pair(xin, yin)); dis[xin][yin] = 0; while(!q.empty()){ cord temp = q.front(); q.pop(); int i = temp.first; int j = temp.second; if ( i - 2 >= 0 && j - 1 >= 0 && dis[i-2][j-1] == -1 ){ dis[i-2][j-1] = dis[i][j] + 1; par[i-2][j-1] = make_pair(i, j); mov[i-2][j-1] = "UL"; q.push(make_pair(i-2, j-1)); if (i-2 == xo && j-1 == yo) break; } if ( i - 2 >= 0 && j + 1 < n && dis[i-2][j+1] == -1 ){ dis[i-2][j+1] = dis[i][j] + 1; par[i-2][j+1] = make_pair(i, j); mov[i-2][j+1] = "UR"; q.push(make_pair(i-2, j+1)); if (i-2 == xo && j+1 == yo) break; } if (j + 2 < n && dis[i][j+2] == -1 ){ dis[i][j+2] = dis[i][j] + 1; par[i][j+2] = make_pair(i, j); mov[i][j+2] = "R"; q.push(make_pair(i, j+2)); if (i == xo && j+2 == yo) break; } if ( i + 2 < n && j + 1 < n && dis[i+2][j+1] == -1 ){ dis[i+2][j+1] = dis[i][j] + 1; par[i+2][j+1] = make_pair(i, j); mov[i+2][j+1] = "LR"; q.push(make_pair(i+2, j+1)); if (i+2 == xo && j+1 == yo) break; } if ( i + 2 < n && j - 1 >= 0 && dis[i+2][j-1] == -1 ){ dis[i+2][j-1] = dis[i][j] + 1; par[i+2][j-1] = make_pair(i, j); mov[i+2][j-1] = "LL"; q.push(make_pair(i+2, j-1)); if (i+2 == xo && j-1 == yo) break; } if (j - 2 >= 0 && dis[i][j-2] == -1 ){ dis[i][j-2] = dis[i][j] + 1; par[i][j-2] = make_pair(i, j); mov[i][j-2] = "L"; q.push(make_pair(i, j-2)); if (i == xo && j-2 == yo) break; } } if (dis[xo][yo] == -1) cout << "Impossible"; else { cout << dis[xo][yo] << endl; printpath(xo, yo, par, mov); } return 0; }