#include #include #include #include #include #include #include #include using coord_t = short; struct point_t { point_t( coord_t _x = 0, coord_t _y = 0 ) : x( _x ), y( _y ) { } coord_t x, y; }; bool operator ==( const point_t &_left, const point_t &_right ) { return _left.x == _right.x && _left.y == _right.y; } bool operator !=( const point_t &_left, const point_t &_right ) { return !( _left == _right ); } std::istream &operator >>( std::istream &_istr, point_t &_point ) { return _istr >> _point.x >> _point.y; } using distance_t = unsigned int; distance_t dist( const point_t &_left, const point_t &_right ) { return std::abs( _left.x - _right.x ) + std::abs( _left.y - _right.y ); } struct direct_t : private point_t { direct_t( coord_t _x, coord_t _y, const char *_name ) : point_t( _x, _y ), name( _name ) { } using point_t::x; using point_t::y; const char *name; }; point_t operator +( const point_t &_point, const direct_t &_direct ) { return { coord_t( _point.x + _direct.x ), coord_t( _point.y + _direct.y ) }; } point_t operator +( const direct_t &_direct, const point_t &_point ) { return _point + _direct; } struct neighbour_t : point_t { neighbour_t( ) : point_t( ), name( nullptr ) { } neighbour_t( point_t &&_point, const char *_name ) : point_t( std::move( _point ) ), name( _name ) { } const char *name; }; struct neighbours_t { struct iterator { using iterator_category = std::input_iterator_tag; using value_type = neighbour_t; using difference_type = std::ptrdiff_t; using pointer = const value_type *; using reference = value_type; iterator( const point_t &_origin, unsigned char _index ) : origin_( _origin ), index_( _index ) { } reference operator *( ) const { return { origin_ + shifts_[index_], shifts_[index_].name }; } iterator &operator ++( ) { ++index_; return *this; } iterator operator ++( int ) { iterator tmp = *this; ++*this; return tmp; } bool operator ==( const iterator &_other ) const { return origin_ == _other.origin_ && index_ == _other.index_; } bool operator !=( const iterator &_other ) const { return !( *this == _other ); } private: static const std::array shifts_; const point_t &origin_; unsigned char index_; }; neighbours_t( const point_t &_origin ) : origin_( _origin ) { } iterator begin( ) const { return iterator( origin_, 0 ); } iterator end( ) const { return iterator( origin_, 6 ); } private: point_t origin_; }; const std::array neighbours_t::iterator::shifts_ = { { { -2, -1, "UL" }, { -2, +1, "UR" }, { 0, +2, "R" }, { +2, +1, "LR" }, { +2, -1, "LL" }, { 0, -2, "L" } } }; bool check( coord_t _bound, const point_t &_point ) { return 0 <= _point.x && _point.x <= _bound && 0 <= _point.y && _point.y <= _bound; } using path_t = std::vector; std::ostream &operator <<( std::ostream &_ostr, const path_t &_path ) { if ( _path.size( ) ) { _ostr << _path.size( ) << std::endl; for ( const char *step : _path ) _ostr << step << ' '; } else _ostr << "Impossible" << std::endl; return _ostr; } neighbour_t step( const point_t &_dept, const point_t &_dest, coord_t _bound ) { neighbour_t curneigh; distance_t curdist = std::numeric_limits::max( ); for ( const neighbour_t &test : neighbours_t( _dept ) ) if ( check( _bound, test ) && dist( test, _dest ) < curdist ) { curneigh = test; curdist = dist( test, _dest ); } return curneigh; } path_t path( const point_t &_dept, const point_t &_dest, coord_t _bound ) { point_t previous = _dept; neighbour_t current = step( _dept, _dest, _bound ); distance_t curdist = dist( current, _dest ); path_t result{ current.name }; while ( curdist && curdist < dist( previous, _dest ) ) { previous = current; current = step( current, _dest, _bound ); curdist = dist( current, _dest ); result.push_back( current.name ); } return curdist ? path_t( ) : result; } int main( ) { coord_t bound; std::cin >> bound; point_t dept, dest; std::cin >> dept >> dest; std::cout << path( dept, dest, bound ) << std::endl; }