Q08 優秀な掃除ロボット

C#のソース

using System;
using System.Collections.Generic;

class Program
{
    //const int LevelLimit = 3;
    const int LevelLimit = 12;

    struct JyoutaiDef
    {
        internal int Level;
        internal int CurrX;
        internal int CurrY;
        internal HashSet<string> VisitedSet;
    }

    static void Main()
    {
        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.Level = 0;
        WillPush.CurrX = WillPush.CurrY = 0;
        WillPush.VisitedSet = new HashSet<string>();
        WillPush.VisitedSet.Add(string.Format("({0},{1})", 0, 0));
        stk.Push(WillPush);

        int AnswerCnt = 0;
        while (stk.Count > 0) {
            JyoutaiDef Popped = stk.Pop();

            //クリア判定
            if (Popped.Level == LevelLimit) {
                AnswerCnt++;
                continue;
            }

            Action<int, int> PushSyori = (pNewX, pNewY) =>
            {
                //再訪不可
                string CurrStr = string.Format("({0},{1})", pNewX, pNewY);
                if (Popped.VisitedSet.Contains(CurrStr)) return;

                WillPush.Level = Popped.Level + 1;
                WillPush.CurrX = pNewX;
                WillPush.CurrY = pNewY;
                WillPush.VisitedSet = new HashSet<string>(Popped.VisitedSet);
                WillPush.VisitedSet.Add(CurrStr);
                stk.Push(WillPush);
            };

            PushSyori(Popped.CurrX, Popped.CurrY - 1);

            //初手は上のみ移動可として、計算量を減らす
            if (Popped.Level == 0) continue;

            PushSyori(Popped.CurrX, Popped.CurrY + 1);
            PushSyori(Popped.CurrX - 1, Popped.CurrY);
            PushSyori(Popped.CurrX + 1, Popped.CurrY);
        }
        Console.WriteLine(AnswerCnt * 4);
    }
}

実行結果

324932

解説

再訪不可な深さ優先探索で解いてます。