Q59 ハンカチ落としの総走行距離

C#のソース

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

class Program
{
    static int UB;

    static void Main()
    {
        //Solve(4, 100);
        //Solve(6, 100);
        Solve(8, 100);
    }

    struct JyoutaiDef
    {
        internal int[] BanArr;
        internal int Level;
        internal int OniNum;
        internal int OniInd;
        internal int SumKyori;
        internal List<string> Log;
    }

    static void Solve(int pN, int pLimitSumKyori)
    {
        UB = pN - 1;

        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.BanArr = Enumerable.Range(1, pN).ToArray();
        WillPush.Level = 0;
        WillPush.OniNum = 0;
        WillPush.OniInd = 0;
        WillPush.SumKyori = 0;
        WillPush.Log = new List<string>();
        WillPush.Log.Add(CreateStrBanInfo(WillPush));

        //1番を鬼に設定
        WillPush.BanArr[0] = 0;
        WillPush.Level = 1;
        WillPush.OniNum = 1;
        WillPush.OniInd = 0;
        WillPush.SumKyori = pN;
        WillPush.Log.Add(CreateStrBanInfo(WillPush));

        stk.Push(WillPush);

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

            //クリア判定
            if (IsClearBan(pN, Popped.BanArr)) {
                if (Popped.SumKyori < AnswerSumKyori) {
                    AnswerSumKyori = Popped.SumKyori;
                    Console.WriteLine("総走行距離={0}の解候補を発見", AnswerSumKyori);
                    Popped.Log.ForEach(X => Console.WriteLine(X));
                }
                continue;
            }

            //下限値枝切り
            if (Popped.SumKyori + pN + 1 >= AnswerSumKyori)
                continue;

            //鬼の走行距離でループ
            for (int I = 1; I <= pN - 1; I++) {
                int NewOniInd = Popped.OniInd + I;
                if (UB < NewOniInd) {
                    NewOniInd -= (UB + 1);
                }
                WillPush.BanArr = (int[])Popped.BanArr.Clone();
                WillPush.BanArr[NewOniInd] = Popped.OniNum;
                WillPush.Level = Popped.Level + 1;
                WillPush.OniNum = Popped.BanArr[NewOniInd];
                WillPush.OniInd = NewOniInd;
                WillPush.SumKyori = Popped.SumKyori + pN + I;
                WillPush.Log = new List<string>(Popped.Log);
                WillPush.Log.Add(CreateStrBanInfo(WillPush));
                stk.Push(WillPush);
            }
        }
    }

    //クリア状態の盤面かをチェック
    static bool IsClearBan(int pN, int[] pBanArr)
    {
        if (pBanArr.Contains(0)) return false;

        var NumList = new List<int>();
        int StaInd = Array.FindIndex(pBanArr, X => X == pN);
        for (int I = StaInd; I <= UB; I++) {
            NumList.Add(pBanArr[I]);
        }
        for (int I = 0; I <= StaInd - 1; I++) {
            NumList.Add(pBanArr[I]);
        }
        return NumList.SequenceEqual(Enumerable.Range(1, pN).Reverse());
    }

    //盤面の情報を返す
    static string CreateStrBanInfo(JyoutaiDef pJyoutai)
    {
        var sb = new System.Text.StringBuilder();
        sb.AppendFormat("Level={0},SumKyori={1}", pJyoutai.Level, pJyoutai.SumKyori);
        sb.AppendLine();

        for (int I = 0; I <= pJyoutai.BanArr.GetUpperBound(0); I++) {
            if (I == pJyoutai.OniInd) {
                sb.Append(pJyoutai.OniNum);
            }
            else sb.Append("  ");
        }
        sb.AppendLine();

        for (int I = 0; I <= pJyoutai.BanArr.GetUpperBound(0); I++) {
            sb.Append(pJyoutai.BanArr[I]);
            if (I < pJyoutai.BanArr.GetUpperBound(0))
                sb.Append(",");
        }
        sb.AppendLine();
        return sb.ToString();
    }
}

実行結果

省略
総走行距離=96の解候補を発見
Level=0,SumKyori=0
0
1,2,3,4,5,6,7,8

Level=1,SumKyori=8
1
0,2,3,4,5,6,7,8

Level=2,SumKyori=21
          6
0,2,3,4,5,1,7,8

Level=3,SumKyori=33
  2
0,6,3,4,5,1,7,8

Level=4,SumKyori=44
        5
0,6,3,4,2,1,7,8

Level=5,SumKyori=58
    3
0,6,5,4,2,1,7,8

Level=6,SumKyori=68
        2
0,6,5,4,3,1,7,8

Level=7,SumKyori=77
          1
0,6,5,4,3,2,7,8

Level=8,SumKyori=86
            7
0,6,5,4,3,2,1,8

Level=9,SumKyori=96
0
7,6,5,4,3,2,1,8

解説

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