Q62 交差せずに一筆書き

C#のソース

using System;
using System.Collections.Generic;

class Program
{
    const int UB_X = 5 - 1;
    const int UB_Y = 4 - 1;

    struct JyoutaiDef
    {
        internal int StaX;
        internal int StaY;
        internal int CurrX;
        internal int CurrY;
        internal int Level;
        internal bool[,] VisitedArr;
    }

    static void Main()
    {
        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;

        //0123なら 01が始点OK
        //01234なら 012が始点OK
        //UB/2までがOKな始点
        //計算量は1/2*1/2=1/4 となる。
        for (int X = 0; X <= UB_X / 2; X++) {
            for (int Y = 0; Y <= UB_Y / 2; Y++) {
                WillPush.StaX = WillPush.CurrX = X;
                WillPush.StaY = WillPush.CurrY = Y;
                WillPush.Level = 1;
                WillPush.VisitedArr = new bool[UB_X + 1, UB_Y + 1];
                WillPush.VisitedArr[X, Y] = true;
                stk.Push(WillPush);
            }
        }

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

            //クリア判定
            if (Popped.Level == (UB_X + 1) * (UB_Y + 1)) {
                //始点との対称点があれば、場合の数を調整
                int wkCnt = 1;
                if (UB_X - Popped.StaX != Popped.StaX) wkCnt *= 2;
                if (UB_Y - Popped.StaY != Popped.StaY) wkCnt *= 2;
                AnswerCnt += wkCnt;
                continue;
            }

            Action<int, int> PushSyori = (pNewX, pNewY) =>
            {
                if (pNewX < 0 || UB_X < pNewX) return;
                if (pNewY < 0 || UB_Y < pNewY) return;

                //再訪不可
                if (Popped.VisitedArr[pNewX, pNewY]) return;

                WillPush.StaX = Popped.StaX;
                WillPush.StaY = Popped.StaY;
                WillPush.CurrX = pNewX;
                WillPush.CurrY = pNewY;
                WillPush.Level = Popped.Level + 1;
                WillPush.VisitedArr = (bool[,])Popped.VisitedArr.Clone();
                WillPush.VisitedArr[pNewX, pNewY] = true;
                stk.Push(WillPush);
            };

            PushSyori(Popped.CurrX, Popped.CurrY - 1);
            PushSyori(Popped.CurrX, Popped.CurrY + 1);
            PushSyori(Popped.CurrX - 1, Popped.CurrY);
            PushSyori(Popped.CurrX + 1, Popped.CurrY);
        }
        //始点と終点を区別しないので、2で割る
        Console.WriteLine(AnswerCnt / 2);
    }
}

実行結果

1006

解説

探索の始点を限定して、計算量を減らしてます。