9019번: DSLR

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

풀이

S 는 n에서 1 을 뺀 결과 n-1을 레지스터에 저장한다. n이 0 이라면 9999 가 대신 레지스터에 저장된다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <memory.h>

using namespace std;

int Check[10001];

int main()
{
	//freopen("input.txt", "rt", stdin);

	int CntCase{}, Start{}, Goal{};

	cin >> CntCase;

	for (int i{}; i < CntCase; ++i)
	{
		cin >> Start >> Goal;

		memset(Check, 0, sizeof(int) * 10001);

		queue<pair<int, string>> Q;
		Q.push(make_pair(Start, ""));
		Check[Start] = 1;

		while (!Q.empty())
		{
			int CurrentInteger = Q.front().first;
			string CurrentString = Q.front().second;
			Q.pop();

			if (CurrentInteger == Goal)
			{
				cout << CurrentString << '\n';
				break;
			}

			// D
			int CheckInteger = (CurrentInteger << 1) % 10000;
			if (0 == Check[CheckInteger])
			{
				Q.push(make_pair(CheckInteger, CurrentString + "D"));
				Check[CheckInteger] = 1;
			}

			// S
			CheckInteger = (0 == CurrentInteger) ? 9999 : CurrentInteger - 1;
			if (0 == Check[CheckInteger])
			{
				Q.push(make_pair(CheckInteger, CurrentString + "S"));
				Check[CheckInteger] = 1;
			}

			// L
			CheckInteger = (CurrentInteger % 1000) * 10 + (CurrentInteger / 1000);
			if (0 == Check[CheckInteger])
			{
				Q.push(make_pair(CheckInteger, CurrentString + "L"));
				Check[CheckInteger] = 1;
			}

			// R
			CheckInteger = (CurrentInteger % 10) * 1000 + (CurrentInteger / 10);
			if (0 == Check[CheckInteger])
			{
				Q.push(make_pair(CheckInteger, CurrentString + "R"));
				Check[CheckInteger] = 1;
			}
		}
	}

	return 0;
}