ABC161-D Lunlun Number

問題へのリンク

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("15");
            //23
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("1");
            //1
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("13");
            //21
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("100000");
            //3234566667
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct JyoutaiDef
    {
        internal string CurrStr;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        long K = long.Parse(InputList[0]);

        var Que = new Queue<JyoutaiDef>();
        JyoutaiDef WillEnqueu;
        for (int I = 1; I <= 9; I++) {
            WillEnqueu.CurrStr = I.ToString();
            Que.Enqueue(WillEnqueu);
        }

        long Banme = 0;
        while (Que.Count > 0) {
            JyoutaiDef Dequeued = Que.Dequeue();
            if (++Banme == K) {
                Console.WriteLine(Dequeued.CurrStr);
                return;
            }

            char LastNum = Dequeued.CurrStr.ToCharArray().Last();
            for (char I = '0'; I <= '9'; I++) {
                if (Math.Abs(LastNum - I) <= 1) {
                    WillEnqueu.CurrStr = Dequeued.CurrStr + I.ToString();
                    Que.Enqueue(WillEnqueu);
                }
            }
        }
    }
}

解説

キューを用意して、
ルンルン数の昇順でデキューされるような幅優先探索で解いてます。