boj-9019

created : 2021-06-27T18:23:08+00:00
modified : 2021-06-27T18:26:20+00:00

C#

using System;
using System.Text;
using System.Collections.Generic;
Dictionary<int, (int BeforeNum, char BeforeCalc)> history = new();
	
int t = int.Parse(Console.ReadLine());
for (int i = 0; i < t; i++)
{
	string[] input = Console.ReadLine().Split(' ');
	
	int a = int.Parse(input[0]);
	int b = int.Parse(input[1]);
	
	history.Clear();
    history[a] = (0, '\0');

	Queue<int> q = new Queue<int>();
    q.Enqueue(a);
	
	while (!history.ContainsKey(b))
	{
		int num = q.Dequeue();
        
			int d = (2 * num) % 10000;
			int s = (num + 9999) % 10000;
			int l = (num / 1000 + 10 * num) % 10000;
			int r = 1000 * (num % 10) + num / 10;
			
			if (!history.ContainsKey(d))
			{
				history[d] = (num, 'D');
				if (d == b) break;
                q.Enqueue(d);
			}
			
			if (!history.ContainsKey(s))
			{
				history[s] = (num, 'S');
                if (s == b) break;
				q.Enqueue(s);
			}
			
			if (!history.ContainsKey(l))
			{
				history[l] = (num, 'L');
				if (l == b) break;
                q.Enqueue(l);
			}
			
			if (!history.ContainsKey(r))
			{
				history[r] = (num, 'R');
                if (r == b) break;
				q.Enqueue(r);
			}
	}
	
	StringBuilder outputBuilder = new();
	for (int before = b; before != a; before = history[before].BeforeNum)
		outputBuilder.Append(history[before].BeforeCalc);
    char[] charArray = outputBuilder.ToString().ToCharArray();
    Array.Reverse(charArray);
	Console.WriteLine(new string(charArray));
}
using System;
using System.Text;
using System.Collections.Generic;

int t = int.Parse(Console.ReadLine());
Dictionary<int, (int BeforeNum, char BeforeCalc)> history = new();
for (int i = 0; i < t; i++)
{
	string[] input = Console.ReadLine().Split(' ');
	
	int a = int.Parse(input[0]);
	int b = int.Parse(input[1]);
	history.Clear();
    history[a] = (a, '\0');

	SortedSet<int> beforeSet = new() { a };
	
	while (!history.ContainsKey(b))
	{
		SortedSet<int> tempSet = new();
		
		foreach (int num in beforeSet)
		{
			int d = (2 * num) % 10000;
			int s = (num + 9999) % 10000;
			int l = (num / 1000 + 10 * num) % 10000;
			int r = 1000 * (num % 10) + num / 10;
			
			if (!history.ContainsKey(d))
			{
				history[d] = (num, 'D');
                if (d == b) break;
				tempSet.Add(d);
			}
			
			if (!history.ContainsKey(s))
			{
				history[s] = (num, 'S');
                if (s == b) break;
				tempSet.Add(s);
			}
			
			if (!history.ContainsKey(l))
			{
				history[l] = (num, 'L');
                if (l == b) break;
				tempSet.Add(l);
			}
			
			if (!history.ContainsKey(r))
			{
				history[r] = (num, 'R');
                if (r == b) break;
				tempSet.Add(r);
			}
		}
		
		beforeSet = tempSet;
	}
	
	StringBuilder outputBuilder = new();
	for (int before = b; before != a; before = history[before].BeforeNum)
		outputBuilder.Append(history[before].BeforeCalc);
    char[] charArray = outputBuilder.ToString().ToCharArray();
    Array.Reverse(charArray);
	Console.WriteLine(new string(charArray));
}