[백준/ 9019] DSLR

#include <iostream>
#include <string>
#include <queue>
using namespace std;
typedef pair<int,string> pis;
const int MAX=10000;
int A,B,dp[MAX+1];
void bfs(){
	queue<pis> q;
	q.push(make_pair(A,""));
	for(int i=0;i<=MAX;i++) dp[i]=1e9;
	dp[A]=0;
	while(!q.empty()){
		pis p = q.front(); q.pop();		
		if( p.first == B ) {
			cout<<p.second<<"\n";
			break;
		}		
		int next = (p.first * 2 >= MAX) ? (p.first * 2) % MAX : p.first * 2;		
		if( dp[next] > dp[p.first] + 1 ){
			dp[next] = dp[p.first] + 1;			
			q.push(make_pair(next,p.second + "D"));
		}
		next = (p.first == 0) ? 9999 : p.first -1;
		if( dp[next] > dp[p.first] + 1 ){
			dp[next] = dp[p.first] + 1;
			q.push(make_pair(next,p.second + "S"));
		}		
		int msb = p.first / 1000;
		next = (p.first * 10) % 10000;
		next += msb;		
		if( dp[next] > dp[p.first] + 1 ){
			dp[next] = dp[p.first] + 1;
			q.push(make_pair(next,p.second + "L"));
		}
		int lsb = (p.first % 10) * 1000;
		next = p.first / 10;
		next += lsb;		
		if( dp[next] > dp[p.first] + 1 ){
			dp[next] = dp[p.first] + 1;
			q.push(make_pair(next,p.second + "R"));
		}
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int T; cin>>T;
	while(T--){
		cin>>A>>B;
		bfs();
	}
	return 0;
}