9019 DSLR

https://www.acmicpc.net/problem/9019

정수 A에서 D,S,L,R 연산을 쓰면서 정수 B를 만드려고 할 때 최소 연산 횟수를 구하는 문제이다. BFS로 구할 수 있다. 큐에 (int 정수,string 지금까지 쓴 명령어)를 넣으면서 답을 찾는다.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <queue>
using namespace std;
 
int a,b;
bool visit[10001];
 
void bfs()
{
    queue<pair<int,string>> q;
    q.push({a,""});
    visit[a]=true;
 
    while(!q.empty())
    {
        auto now=q.front(); q.pop();
        int n=now.first;
        string t=now.second;
 
        if(n==b)
        {
            cout<<t<<'\n';
            return;
        }
 
        // D 명령어 수행
        int next=2*n;
        if(2*n>9999) next=(2*n)%10000;
        if(!visit[next])
        {
            visit[next]=true;
            q.push({next,t+"D"});
        }
 
        // S 명령어 수행
        if(n==0) next=9999;
        else next=n-1;
        if(!visit[next])
        {
            visit[next]=true;
            q.push({next,t+"S"});
        }
 
        // 각 자리수 구하기
        int temp=n;
        int d[4];
        for(int i=3;i>=0;i--)
        {
            d[i]=temp%10;
            temp/=10;
        }
 
        // L 명령어 수행
        next=d[1]*1000+d[2]*100+d[3]*10+d[0];
        if(!visit[next])
        {
            visit[next]=true;
            q.push({next,t+"L"});
        }
 
        // R 명령어 수행
        next=d[3]*1000+d[0]*100+d[1]*10+d[2];
        if(!visit[next])
        {
            visit[next]=true;
            q.push({next,t+"R"});
        }
    }
}
 
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d %d",&a,&b);
        bfs();
        memset(visit,0,sizeof(visit));
    }
    return 0;
}