[BOJ] 9019. DSLR

#include <iostream>
#include <queue>
#include <cstring>
#include <vector>
#define mod 10000
#define p pair<int, string>
using namespace std;

int visit[mod];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int tc;
    cin >> tc;
    for(int i=0; i<tc; i++){
        memset(visit,0,sizeof(visit));
        int st;
        int dest;
        cin >> st >> dest;
        
        queue<p> q;
        q.push({st,""});
        
        while (! q.empty()) {
            int top = q.front().first;
            string operation = q.front().second;
            q.pop();
            
            if( top == dest) {
                cout << operation << endl;
                break;
            }

            int _top = top;
            operation += "D";
            if( ! visit[_top * 2 % mod] )
                q.push( { _top * 2 % mod, operation } );
            visit[ _top * 2 % mod ] = 1;
            operation.pop_back();
            
            _top = _top == 0 ? 9999 : _top - 1;
            operation += "S";
            if( ! visit[_top ] )
                q.push( { _top, operation } );
            visit[ _top ] = 1;
            operation.pop_back();
            
            operation += "L";
            _top = top / 1000;
            _top += top % 1000 * 10;
            if( ! visit[_top ] )
                q.push( {_top, operation } );
            visit[ _top ] = 1;
            operation.pop_back();
            
            operation += "R";
            _top = top % 10;
            _top = (top / 10) + (_top * 1000);
            if( ! visit[_top ] )
                q.push( { _top, operation } );
            visit[ _top ] = 1;
            operation.pop_back();
            
        } // end of while
    } // end of for i
    
    return 0;
}