C++

#include <cstdio>

#include <queue>

#include <algorithm>

#include <cstring>

#include <cstdlib>

using namespace std;

struct Q_info{

    int n;

};

queue<Q_info> q;

int N;

char result[10010][10010];

int check[10010];

int memory[10010][2];

void ClearQueue(queue<Q_info> &someQueue)

{

    queue<Q_info> empty_;

    swap(someQueue, empty_);

}

void reverseString(char* s) {

  size_t size_ = strlen(s);

  char temp;

 

  for (size_t i = 0; i < size_ / 2; i++) {

    temp = s[i];

    s[i] = s[(size_ - 1) - i];

    s[(size_ - 1) - i] = temp;

  }

}

int main()

{

    scanf("%d",&N);

    for(int i=0;i<N;i++){

        int f,b;

        scanf("%d %d",&f,&b);

        ClearQueue(q);

        memset(check,0,sizeof(check));

        memset(memory,0,sizeof(memory));

        q.push({f});

        check[f]=1;

        while(!q.empty()){

            Q_info a=q.front();

            q.pop();

            if(a.n==b){

                //result[i]=a.path;

                break;

            }

            if(check[(a.n*2)%10000]==0){

                check[(a.n*2)%10000]=1;

                q.push({(a.n*2)%10000});//1==d

                memory[(a.n*2)%10000][0]=a.n;

                memory[(a.n*2)%10000][1]=1;

            }

            if(a.n==0){

                if(check[9999]==0){

                    check[9999]=1;

                    q.push({9999});

                    memory[9999][0]=a.n;

                    memory[9999][1]=2;

                }

            }else{

                if(check[a.n-1]==0){

                    check[a.n-1]=1;

                    q.push({a.n-1});

                    memory[a.n-1][0]=a.n;

                    memory[a.n-1][1]=2;

                }

            }

            int num=a.n%10;

            if(check[a.n/10+num*1000]==0){

                check[a.n/10+num*1000]=1;

                q.push({a.n/10+num*1000});

                memory[a.n/10+num*1000][0]=a.n;

                memory[a.n/10+num*1000][1]=4;

            }

            num=a.n/1000;

            if(check[a.n%1000*10+num]==0){

                check[a.n%1000*10+num]=1;

                q.push({a.n%1000*10+num});

                memory[a.n%1000*10+num][0]=a.n;

                memory[a.n%1000*10+num][1]=3;

            }

 

        }

        int idx=b;

        int idx_s=0;

        while(1){

            if(memory[idx][1]==0){

                break;

            }

            switch(memory[idx][1]){

            case 1:

                result[i][idx_s]='D';

                break;

            case 2:

                result[i][idx_s]='S';

                break;

            case 3:

                result[i][idx_s]='L';

                break;

            case 4:

                result[i][idx_s]='R';

                break;

            }

            idx_s++;

            idx=memory[idx][0];

        }

    }

    for(int i=0;i<N;i++){

        reverseString(result[i]);

        printf("%s\n",result[i]);

    }

    return 0;

}