Q50 急がば回れ

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    const int UB_X = 6;
    const int UB_Y = 5;

    struct JyoutaiDef
    {
        internal int Level;
        internal int CurrX;
        internal int CurrY;
        internal List<int> UsedSameXList;
        internal List<int> UsedSameYList;
        internal string Log;
    }

    static void Main()
    {
        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.Level = 0;
        WillPush.CurrX = WillPush.CurrY = 0;
        WillPush.UsedSameXList = new List<int>();
        WillPush.UsedSameYList = new List<int>();
        WillPush.Log = string.Format("({0},{1})", WillPush.CurrX, WillPush.CurrY);
        stk.Push(WillPush);

        int AnswerLevel = int.MinValue;

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

            //クリア判定
            if (Popped.CurrX == UB_X && Popped.CurrY == UB_Y) {
                if (AnswerLevel < Popped.Level) {
                    AnswerLevel = Popped.Level;
                    Console.WriteLine("レベル={0}の解候補を発見", AnswerLevel);
                    Console.WriteLine(Popped.Log);
                }
                continue;
            }

            Action<int, int> PushSyori = (pNewX, pNewY) =>
            {
                //対称解の除外で最初は、横に移動
                if (Popped.Level == 0 && pNewX != 1) return;

                if (pNewX < 0 || UB_X < pNewX) return;
                if (pNewY < 0 || UB_Y < pNewY) return;

                //同じ直線上は2回まで移動可
                if (Popped.CurrX == pNewX) {
                    if (Popped.UsedSameXList.Count(A => A == pNewX) >= 2) return;
                    WillPush.UsedSameXList = new List<int>(Popped.UsedSameXList) { pNewX };
                    WillPush.UsedSameYList = Popped.UsedSameYList;
                }
                else {
                    if (Popped.UsedSameYList.Count(A => A == pNewY) >= 2) return;
                    WillPush.UsedSameXList = Popped.UsedSameXList;
                    WillPush.UsedSameYList = new List<int>(Popped.UsedSameYList) { pNewY };
                }

                WillPush.Level = Popped.Level + 1;
                WillPush.CurrX = pNewX;
                WillPush.CurrY = pNewY;
                WillPush.Log = Popped.Log + "," + string.Format("({0},{1})", pNewX, pNewY);
                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);
        }
    }
}

実行結果

レベル=17の解候補を発見
(0,0),(1,0),(2,0),(2,1),(3,1),(4,1),(4,2),(5,2),(6,2),(6,3),
(5,3),(6,3),(6,4),(5,4),(4,4),(4,5),(5,5),(6,5)
レベル=19の解候補を発見
(0,0),(1,0),(2,0),(2,1),(3,1),(4,1),(4,2),(5,2),(6,2),(6,3),
(5,3),(6,3),(6,4),(5,4),(4,4),(4,5),(5,5),(5,4),(5,5),(6,5)
レベル=21の解候補を発見
(0,0),(1,0),(2,0),(2,1),(3,1),(4,1),(4,2),(5,2),(6,2),(6,3),
(5,3),(5,4),(4,4),(4,3),(3,3),(3,4),(3,5),(4,5),(5,5),(5,4),
(6,4),(6,5)
レベル=23の解候補を発見
(0,0),(1,0),(2,0),(2,1),(3,1),(4,1),(4,2),(3,2),(2,2),(2,3),
(1,3),(1,4),(1,5),(2,5),(3,5),(3,4),(3,3),(4,3),(4,4),(5,4),
(5,5),(5,4),(6,4),(6,5)
レベル=25の解候補を発見
(0,0),(1,0),(2,0),(2,1),(3,1),(3,2),(2,2),(1,2),(1,3),(1,4),
(0,4),(0,5),(1,5),(2,5),(2,4),(3,4),(3,3),(4,3),(4,2),(4,1),
(5,1),(5,2),(5,3),(6,3),(6,4),(6,5)

解説

深さ優先探索で解いてます。