#include #include #include #include #include #include #include using namespace std; using uint = unsigned int; using ll = long long; #define CIN( LL , A ) LL A; cin >> A #define GETLINE( A ) string A; getline( cin , A ) #define GETLINE_SEPARATE( A , SEPARATOR ) string A; getline( cin , A , SEPARATOR ) #define FOR_LL( VAR , INITIAL , FINAL_PLUS_ONE ) for( ll VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ ) #define FOR_ITR( ARRAY , ITR , END ) for( auto ITR = ARRAY .begin() , END = ARRAY .end() ; ITR != END ; ITR ++ ) #define REPEAT( HOW_MANY_TIMES ) FOR_LL( VARIABLE_FOR_REPEAT , 0 , HOW_MANY_TIMES ) #define RETURN( ANSWER ) cout << ( ANSWER ) << endl; return 0 #define DOUBLE( PRECISION , ANSWER ) cout << fixed << setprecision( PRECISION ) << ( ANSWER ) << endl; return 0 #define MIN( A , B ) A < B ? A : B; #define MAX( A , B ) A < B ? B : A; template inline T Distance( const T& a , const T& b ){ return a < b ? b - a : a - b; } #include // 自分のライブラリ(https://github.com/p-adic/cpp)よりソースコードをコピーして編集している。 template class AffineSpace { private: T m_v[D]; public: inline AffineSpace(); inline AffineSpace( const initializer_list init ); template inline AffineSpace( const T (&v)[E] ); template inline AffineSpace( const AffineSpace& x ); // E < Dの場合のみサポート template inline AffineSpace( const uint& E , const ARGS&... args ); template inline AffineSpace& operator=( const AffineSpace& x ); T& operator[]( const uint& i ); const T& operator[]( const uint& i ) const; private: template void Set( const T (&v)[E] ); void Substitute( const initializer_list init ); template void Substitute( const T (&v)[E] ); template void Substitute( const AffineSpace& x ); }; template inline AffineSpace::AffineSpace() : m_v() {}; template inline AffineSpace::AffineSpace( const initializer_list init ) : m_v() { Substitute( init ); } template template inline AffineSpace::AffineSpace( const T (&v)[E] ) : m_v() { Substitute( v ); } template template inline AffineSpace::AffineSpace( const AffineSpace& x ) : m_v() { Substitute( x ); } template template inline AffineSpace::AffineSpace( const uint& E , const ARGS&... args ) : AffineSpace( args... ) { m_v[E]++; } template template inline AffineSpace& AffineSpace::operator=( const AffineSpace& x ) { Set( x.m_v ); return *this; } template inline T& AffineSpace::operator[]( const uint& i ) { return m_v[i]; } template inline const T& AffineSpace::operator[]( const uint& i ) const { return m_v[i]; } template template void AffineSpace::Set( const T (&v)[E] ) { Substitute( v ); constexpr const uint min = E < D ? E : D; for( uint i = min ; i < D ; i++ ){ m_v[i] = 0; } return; } template void AffineSpace::Substitute( const initializer_list init ) { const uint size = init.size(); const uint min = size < D ? size : D; auto itr = init.begin(); for( uint i = 0 ; i < min ; i++ ){ m_v[i] = *itr; itr++; } return; } template template void AffineSpace::Substitute( const T (&v)[E] ) { constexpr const uint min = E < D ? E : D; for( uint i = 0 ; i < min ; i++ ){ m_v[i] = v[i]; } return; } template template void AffineSpace::Substitute( const AffineSpace& x ) { constexpr const uint min = E < D ? E : D; for( uint i = 0 ; i < min ; i++ ){ m_v[i] = x[i]; } return; } #define H 20 #define W 20 #define H_minus 19 #define W_minus 19 #define T 1001 #define K 401 int main() { constexpr const ll D = 0; constexpr const ll R = 1; constexpr const ll U = 2; constexpr const ll L = 3; const string direction[4] = { "D" , "R" , "U" , "L" }; CIN( ll , H_dummy ); CIN( ll , W_dummy ); CIN( ll , p ); bool wall[H][W][4] = {}; FOR_LL( i , 0 , H ){ wall[i][0][L] = true; wall[i][W-1][R] = true; } FOR_LL( j , 0 , W ){ wall[0][j][U] = true; wall[H-1][j][D] = true; } ll fixed_length = 0; ll strategy[K] = {}; ll coord_x[K] = {}; ll coord_y[K] = {}; FOR_LL( t , 0 , T ){ FOR_LL( k , fixed_length + 1 , K ){ const ll& x = coord_x[k]; const ll& y = coord_y[k]; bool (&w)[4] = wall[y][x]; bool searching = true; const ll& s_k_prev = strategy[k-1]; ll& s_k = strategy[k]; s_k = ( s_k_prev + 3 ) % 4; for( ll d = 0 ; d < 4 && searching ; d++ ){ if( ! w[s_k] ){ searching = false; } else { s_k = ( s_k + 1 ) % 4; } } if( searching ){ for( ll d = 0 ; d < 4 ; d++ ){ w[d] = ( x == 0 && d == L ) || ( x == W_minus && d == R ) || ( y == 0 && d == U ) || ( y == H_minus && d == D ); if( x > 0 ){ wall[y][x-1][R] = true; } if( x < H_minus ){ wall[y][x+1][L] = true; } if( y > 0 ){ wall[y-1][x][D] = true; } if( y < W_minus ){ wall[y+1][x][W] = true; } } s_k = ( s_k_prev + 3 ) % 4; for( ll d = 0 ; d < 4 && searching ; d++ ){ if( ! w[s_k] ){ searching = false; } else { s_k = ( s_k + 1 ) % 4; } } } coord_x[k+1] = x + ( s_k == L ? -1 : s_k == R ? 1 : 0 ); coord_y[k+1] = y + ( s_k == U ? -1 : s_k == D ? 1 : 0 ); } FOR_LL( k , 1 , K ){ cout << direction[strategy[k]]; } cout << endl; CIN( ll , length ); if( length == -1 ){ RETURN( 0 ); } if( fixed_length < length ){ fixed_length = length; ll K0 = fixed_length + 1; if( K0 < K ){ const ll& x = coord_x[K0]; const ll& y = coord_y[K0]; const ll& s_K0 = strategy[K0]; wall[y][x][s_K0] = true; if( s_K0 == D || y < H_minus ){ wall[y+1][x][U] = true; } if( s_K0 == R || x < W_minus ){ wall[y][x+1][L] = true; } if( s_K0 == U || y > 0 ){ wall[y-1][x][D] = true; } if( s_K0 == L || x > 0 ){ wall[y][x-1][R] = true; } } FOR_LL( k , 1 , K0 ){ const ll& x = coord_x[k]; const ll& y = coord_y[k]; FOR_LL( m , k + 1 , K0 ){ if( coord_x[m] == x && coord_y[m] == y ){ const ll& s_k = strategy[k]; wall[y][x][s_k] = true; if( s_k == D || y < H_minus ){ wall[y+1][x][U] = true; } if( s_k == R || x < W_minus ){ wall[y][x+1][L] = true; } if( s_k == U || y > 0 ){ wall[y-1][x][D] = true; } if( s_k == L || x > 0 ){ wall[y][x-1][R] = true; } ll d = m - k; fixed_length -= d; K0 -= d; FOR_LL( n , k + 1 , K0 ){ strategy[n] = strategy[n + d]; coord_x[n] = coord_x[n + d]; coord_y[n] = coord_y[n + d]; } } } } } } return 0; }