川添さん問題11 プライム・ホッパー

■■■問題■■■

ある素数に対し、次の変換1と2のいずれかを適用し、新たな素数を作ります。

●変換1 :元の数の右または左に1〜9のいずれかの数字1つをつなげる。
         (例：2→23、13→139、3→13、29→229)
●変換2 :元の数の右端または左端の数字1つを取り除く。
         (元の数が2桁以上の場合のみ。
          例：31→3、673→67、23→3、673→73)

例えば 7→227、17→37 は有効な変換ではありません。
また 103→03 のように、先頭に0のつく数への変換はできません。

さて、素数pとq (p < q) が与えられたときに、
素数pから始めて、変換1または2によりq以下の素数を作るということを繰り返し行い、
最小の変換回数でqを作ることを考えましょう。

p＝5，q＝67 のときの一例を示します。計5回の変換で67に変換できます。
途中の数がいずれも67以下の素数であることに注意して下さい。
なお、必ずしも変換1と2の両方を行う必要はありません。

5　→　53　→　3　→　37　→　7　→　67

素数p,qに対し、pから始めて q を作るときの最小の変換回数を F(p, q) と定義します。
そのような作り方が存在しない場合は F(p, q) = -1と定義します。

例えば F(5, 67) = 5，F(3, 29) = 3，F(5, 541) = 10，F(3, 7)= -1 です。

標準入力から、半角空白区切りで素数 p, q (p < q かつ q <= 10万) が与えられます。
標準出力にF(n)の値を出力するプログラムを書いてください。

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("5 67");
            //5
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3 29");
            //3
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("5 541");
            //10
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("3 7");
            //-1
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static HashSet<string> SosuuSet = new HashSet<string>();

    //エラトステネスの篩で上限以下の素数の配列を返す
    static void Eratosthenes(int pJyougen)
    {
        var IsSosuuArr = new System.Collections.BitArray(pJyougen + 1);
        for (int I = 2; I <= IsSosuuArr.Count - 1; I++) {
            IsSosuuArr[I] = true;
        }
        for (int I = 2; I * I <= IsSosuuArr.Count - 1; I++) {
            if (IsSosuuArr[I] == false) continue;
            for (int J = I * 2; J <= IsSosuuArr.Count - 1; J += I) {
                IsSosuuArr[J] = false;
            }
        }
        for (int I = 2; I <= IsSosuuArr.Count - 1; I++) {
            if (IsSosuuArr[I]) SosuuSet.Add(I.ToString());
        }
    }

    struct JyoutaiDef
    {
        internal string CurrStr;
        internal int Level;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int[] wkArr = InputList[0].Split(' ').Select(X => int.Parse(X)).ToArray();

        int P = wkArr[0];
        int Q = wkArr[1];

        Eratosthenes(Q);

        var Que = new Queue<JyoutaiDef>();
        JyoutaiDef WillEnque;
        WillEnque.CurrStr = P.ToString();
        WillEnque.Level = 0;
        Que.Enqueue(WillEnque);

        int Answer = -1;

        var VisitedSet = new HashSet<string>();
        VisitedSet.Add(WillEnque.CurrStr);

        while (Que.Count > 0) {
            JyoutaiDef Dequeued = Que.Dequeue();

            if (Dequeued.CurrStr == Q.ToString()) {
                Answer = Dequeued.Level;
                break;
            }

            var ConvStrList = new List<string>();
            ConvStrList.AddRange(Conv1(Dequeued.CurrStr));
            ConvStrList.AddRange(Conv2(Dequeued.CurrStr));

            foreach (string EachConvStr in ConvStrList) {
                if (VisitedSet.Add(EachConvStr) == false)
                    continue;

                WillEnque.CurrStr = EachConvStr;
                WillEnque.Level = Dequeued.Level + 1;
                Que.Enqueue(WillEnque);
            }
        }
        Console.WriteLine(Answer);
    }

    //変換1を行った結果のListを返す
    static string[] Conv1(string pBase)
    {
        var WillRerurn = new List<string>();
        for (char I = '1'; I <= '9'; I++) {
            WillRerurn.Add(pBase + I);
            WillRerurn.Add(I + pBase);
        }
        WillRerurn.RemoveAll(X => SosuuSet.Contains(X)==false);
        return WillRerurn.ToArray();
    }

    //変換2を行った結果のListを返す
    static string[] Conv2(string pBase)
    {
        var WillRerurn = new List<string>();
        int wkLen = pBase.Length;
        if (wkLen > 0) {
            WillRerurn.Add(pBase.Substring(1));
            WillRerurn.Add(pBase.Substring(0, wkLen - 1));
        }
        WillRerurn.RemoveAll(X => SosuuSet.Contains(X) == false);
        return WillRerurn.ToArray();
    }
}

解説

幅優先探索で解いてます。