Q27 右折を禁止されても大丈夫？

C#のソース

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var sw = System.Diagnostics.Stopwatch.StartNew();
        Solve(3, 2);
        Solve(6, 4);
        Console.WriteLine("経過時間={0}", sw.Elapsed);
    }

    static int UB_X;
    static int UB_Y;

    struct JyoutaiDef
    {
        internal int Muki; //0が上向き,1が左向き,2が下向き,3が右向き
        internal int CurrX;
        internal int CurrY;
        internal HashSet<string> UsedRoadSet;
        internal string Log;
    }

    static void Solve(int pX, int pY)
    {
        UB_X = pX;
        UB_Y = pY;

        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.Muki = 3;
        WillPush.CurrX = 0;
        WillPush.CurrY = UB_Y;
        WillPush.UsedRoadSet = new HashSet<string>();
        WillPush.Log = string.Format("({0},{1})", WillPush.CurrX, WillPush.CurrY);
        stk.Push(WillPush);

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

            //クリア判定
            if (Popped.CurrX == UB_X && Popped.CurrY == 0) {
                AnswerCnt++;
                //Console.WriteLine("解{0}を発見", AnswerCnt);
                //Console.WriteLine(Popped.Log);
                continue;
            }

            Action<bool> PushSyori = WillSasetu =>
            {
                if (WillSasetu) {
                    WillPush.Muki = (Popped.Muki + 1) % 4;
                }
                else WillPush.Muki = Popped.Muki;

                int HeniX = 0, HeniY = 0;
                if (WillPush.Muki == 0) HeniY = -1; //上向き
                if (WillPush.Muki == 1) HeniX = -1; //左向き
                if (WillPush.Muki == 2) HeniY = 1; //下向き
                if (WillPush.Muki == 3) HeniX = 1; //右向き

                WillPush.CurrX = Popped.CurrX + HeniX;
                WillPush.CurrY = Popped.CurrY + HeniY;

                if (WillPush.CurrX < 0 || UB_X < WillPush.CurrX) return;
                if (WillPush.CurrY < 0 || UB_Y < WillPush.CurrY) return;

                //使用済の道路は使用不可
                string UseRoadStr = UseRoadToStr(Popped.CurrX, Popped.CurrY,
                                                 WillPush.CurrX, WillPush.CurrY);
                if (Popped.UsedRoadSet.Contains(UseRoadStr)) return;
                WillPush.UsedRoadSet = new HashSet<string>(Popped.UsedRoadSet);
                WillPush.UsedRoadSet.Add(UseRoadStr);

                WillPush.Log = Popped.Log + ","
                             + string.Format("({0},{1})", WillPush.CurrX, WillPush.CurrY);

                stk.Push(WillPush);
            };
            PushSyori(false);
            PushSyori(true);
        }
        Console.WriteLine("横{0}、縦{1}での解は{2}通り", pX, pY, AnswerCnt);
    }

    //使用した道路をString型で表現
    static string UseRoadToStr(int pFromX, int pFromY, int pToX, int pToY)
    {
        int MinX = Math.Min(pFromX, pToX);
        int MaxX = Math.Max(pFromX, pToX);

        int MinY = Math.Min(pFromY, pToY);
        int MaxY = Math.Max(pFromY, pToY);

        return string.Format("({0},{1})-({2},{3})", MinX, MinY, MaxX, MaxY);
    }
}

実行結果

横3、縦2での解は4通り
横6、縦4での解は2760通り
経過時間=00:00:01.8786253

解説

深さ優先探索でナイーブに解いてます。