AOJ 0675 テンキー

問題へのリンク(AOJ)
問題へのリンク(AtCoder)

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("100000 13");
            //5
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4 3");
            //3
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long[] GetSplitArr(string pStr)
    {
        return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = GetSplitArr(InputList[0]);
        long Hou = wkArr[0];
        long GoalVal = wkArr[1];

        var Que = new Queue<JyoutaiDef>();
        JyoutaiDef WillEnqueue;
        WillEnqueue.CurrX = 0;
        WillEnqueue.CurrY = 3;
        WillEnqueue.Level = 0;
        WillEnqueue.Val = 0;
        Que.Enqueue(WillEnqueue);

        var VisitedSet = new HashSet<long>();

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

            long Hash = GetHash(Dequeued);
            if (VisitedSet.Add(Hash) == false) {
                continue;
            }

            // クリア判定
            if (Dequeued.Val == GoalVal) {
                Console.WriteLine(Dequeued.Level);
                return;
            }

            // 移動する遷移
            Action<long, long> EnqueueAct = (long pNewX, long pNewY) =>
            {
                // 範囲外はNG
                if (GetNum(pNewX, pNewY) == null) {
                    return;
                }

                WillEnqueue.CurrX = pNewX;
                WillEnqueue.CurrY = pNewY;
                WillEnqueue.Level = Dequeued.Level + 1;
                WillEnqueue.Val = Dequeued.Val;
                Que.Enqueue(WillEnqueue);
            };

            EnqueueAct(Dequeued.CurrX, Dequeued.CurrY - 1);
            EnqueueAct(Dequeued.CurrX, Dequeued.CurrY + 1);
            EnqueueAct(Dequeued.CurrX - 1, Dequeued.CurrY);
            EnqueueAct(Dequeued.CurrX + 1, Dequeued.CurrY);

            // 数値を設定する遷移
            long? CurrNum = GetNum(Dequeued.CurrX, Dequeued.CurrY);
            WillEnqueue.CurrX = Dequeued.CurrX;
            WillEnqueue.CurrY = Dequeued.CurrY;
            WillEnqueue.Level = Dequeued.Level + 1;
            WillEnqueue.Val = Dequeued.Val * 10 + CurrNum.Value;
            WillEnqueue.Val %= Hou;
            Que.Enqueue(WillEnqueue);
        }
    }

    static long GetHash(JyoutaiDef pJyoutai)
    {
        long Hash = 0;
        Hash += pJyoutai.CurrX;
        Hash *= 10;
        Hash += pJyoutai.CurrY;
        Hash *= 1000000;
        Hash += pJyoutai.Val;
        return Hash;
    }

    struct JyoutaiDef
    {
        internal long CurrX;
        internal long CurrY;
        internal long Level;
        internal long Val;
    }

    // 現在座標を引数として、テンキーの値を返す
    // 範囲外ならnullを返す
    static long? GetNum(long pX, long pY)
    {
        if (pY == 0 && pX == 0) return 7;
        if (pY == 0 && pX == 1) return 8;
        if (pY == 0 && pX == 2) return 9;

        if (pY == 1 && pX == 0) return 4;
        if (pY == 1 && pX == 1) return 5;
        if (pY == 1 && pX == 2) return 6;

        if (pY == 2 && pX == 0) return 1;
        if (pY == 2 && pX == 1) return 2;
        if (pY == 2 && pX == 2) return 3;

        if (pY == 3 && pX == 0) return 0;

        return null;
    }
}

解説

BFSしてます。

0から9と
modの値が0から100000 なので、

状態数は
10*100000 = 1000000
なため、{ノード , 余りの値 } で再訪防止でBFSしてます。