8-34 川渡り問題5 船の移動

問題

今、川のこちら岸に４隻の船Ａ，Ｂ，Ｃ，Ｄがあります。
今回の目的は、この４隻の船を全て向こう岸に運ぶことです。

　　　　　 川

船Ａ　｜ ~ ~ ~ ~｜
　　　｜ ~ ~ ~ ~｜
船Ｂ　｜ ~ ~ ~ ~｜
　　　｜ ~ ~ ~ ~｜
船Ｃ　｜ ~ ~ ~ ~｜
　　　｜ ~ ~ ~ ~｜
船Ｄ　｜ ~ ~ ~ ~｜
　　　｜ ~ ~ ~ ~｜

船は１隻ずつ運ぶこともできるし、２隻を同時に運ぶこともできます。
ただし、２隻を同時に運ぶ場合は、遅いほうの船と同じ時間がかかります

船が川を渡るには、それぞれ１分、３分、６分、９分かかるとします。
さて、船を全て運ぶのにかかる最短時間を求めてください。
また、その手順を示してください。

ソース

using System;
using System.Collections.Generic;

class Program
{
    struct JyoutaiDef
    {
        internal bool IsALeft;
        internal bool IsBLeft;
        internal bool IsCLeft;
        internal bool IsDLeft;
        internal bool IsSendouLeft;
        internal List<string> LogList;
        internal List<int> TimeRunSumList;

        internal void Init()
        {
            IsALeft = IsBLeft = IsCLeft = IsDLeft = true;
            IsSendouLeft = true;
            LogList = new List<string>();
            TimeRunSumList = new List<int>() { 0 };
            AddOneLog();
        }

        internal void MakeKishiInfo(bool pIsLeftInfo, System.Text.StringBuilder pSb)
        {
            if (pIsLeftInfo == IsALeft) pSb.Append("船A,");
            if (pIsLeftInfo == IsBLeft) pSb.Append("船B,");
            if (pIsLeftInfo == IsCLeft) pSb.Append("船C,");
            if (pIsLeftInfo == IsDLeft) pSb.Append("船D,");
        }

        internal bool AddOneLog()
        {
            var sb = new System.Text.StringBuilder();
            MakeKishiInfo(true, sb);
            sb.Append(IsSendouLeft ? " 船頭 川川川 " : " 川川川 船頭 ");
            MakeKishiInfo(false, sb);

            string wkStr = sb.ToString();
            if (LogList.Contains(wkStr)) return false;
            LogList.Add(wkStr);
            return true;
        }

        internal void PrintLog()
        {
            for (int I = 0; I <= LogList.Count - 1; I++) {
                Console.WriteLine("レベル{0,2} {1} 合計時間={2}", I, LogList[I], TimeRunSumList[I]);
            }
        }
    }

    static void Main()
    {
        var Jyoutai = new JyoutaiDef();
        Jyoutai.Init();

        var que = new Queue<JyoutaiDef>();
        que.Enqueue(Jyoutai);

        int MaxTimeSum = int.MaxValue;
        int AnswerCnt = 0;
        while (que.Count > 0) {
            Jyoutai = que.Dequeue();
            //Jyoutai.PrintLog();
            int CurrTimeRunSum = Jyoutai.TimeRunSumList[Jyoutai.TimeRunSumList.Count - 1];
            if (CurrTimeRunSum > MaxTimeSum)
                continue;

            if (Jyoutai.IsALeft == false && Jyoutai.IsBLeft == false
             && Jyoutai.IsCLeft == false && Jyoutai.IsDLeft == false
             && Jyoutai.IsSendouLeft == false) {
                Console.WriteLine("解{0}を発見しました。", ++AnswerCnt);
                Jyoutai.PrintLog();
                MaxTimeSum = CurrTimeRunSum;
                continue;
            }

            Action<JyoutaiDef, int> EnqueueSyori = (pWillEnqueue, pKasanVal) =>
            {
                pWillEnqueue.TimeRunSumList = new List<int>(Jyoutai.TimeRunSumList);
                pWillEnqueue.TimeRunSumList.Add(CurrTimeRunSum + pKasanVal);
                pWillEnqueue.LogList = new List<string>(Jyoutai.LogList);
                pWillEnqueue.IsSendouLeft = !Jyoutai.IsSendouLeft;
                if (pWillEnqueue.AddOneLog()) que.Enqueue(pWillEnqueue);
            };

            if (Jyoutai.IsSendouLeft) {
                //船Aと船Bを移動
                if (Jyoutai.IsALeft && Jyoutai.IsBLeft) {
                    JyoutaiDef WillEnqueue = Jyoutai;
                    WillEnqueue.IsALeft = WillEnqueue.IsBLeft = false;
                    EnqueueSyori(WillEnqueue, 3);
                }
                //船Aと船Cを移動
                if (Jyoutai.IsALeft && Jyoutai.IsCLeft) {
                    JyoutaiDef WillEnqueue = Jyoutai;
                    WillEnqueue.IsALeft = WillEnqueue.IsCLeft = false;
                    EnqueueSyori(WillEnqueue, 6);
                }
                //船Aと船Dを移動
                if (Jyoutai.IsALeft && Jyoutai.IsDLeft) {
                    JyoutaiDef WillEnqueue = Jyoutai;
                    WillEnqueue.IsALeft = WillEnqueue.IsDLeft = false;
                    EnqueueSyori(WillEnqueue, 9);
                }
                //船Bと船Cを移動
                if (Jyoutai.IsBLeft && Jyoutai.IsCLeft) {
                    JyoutaiDef WillEnqueue = Jyoutai;
                    WillEnqueue.IsBLeft = WillEnqueue.IsCLeft = false;
                    EnqueueSyori(WillEnqueue, 6);
                }
                //船Bと船Dを移動
                if (Jyoutai.IsBLeft && Jyoutai.IsDLeft) {
                    JyoutaiDef WillEnqueue = Jyoutai;
                    WillEnqueue.IsBLeft = WillEnqueue.IsDLeft = false;
                    EnqueueSyori(WillEnqueue, 9);
                }
                //船Cと船Dを移動
                if (Jyoutai.IsCLeft && Jyoutai.IsDLeft) {
                    JyoutaiDef WillEnqueue = Jyoutai;
                    WillEnqueue.IsCLeft = WillEnqueue.IsDLeft = false;
                    EnqueueSyori(WillEnqueue, 9);
                }
                //船Aを移動
                if (Jyoutai.IsALeft) {
                    JyoutaiDef WillEnqueue = Jyoutai;
                    WillEnqueue.IsALeft = false;
                    EnqueueSyori(WillEnqueue, 1);
                }
                //船Bを移動
                if (Jyoutai.IsBLeft) {
                    JyoutaiDef WillEnqueue = Jyoutai;
                    WillEnqueue.IsBLeft = false;
                    EnqueueSyori(WillEnqueue, 3);
                }
                //船Cを移動
                if (Jyoutai.IsCLeft) {
                    JyoutaiDef WillEnqueue = Jyoutai;
                    WillEnqueue.IsCLeft = false;
                    EnqueueSyori(WillEnqueue, 6);
                }
                //船Dを移動
                if (Jyoutai.IsDLeft) {
                    JyoutaiDef WillEnqueue = Jyoutai;
                    WillEnqueue.IsDLeft = false;
                    EnqueueSyori(WillEnqueue, 9);
                }
            }
            else {
                //船Aと船Bを移動
                if (Jyoutai.IsALeft == false && Jyoutai.IsBLeft == false) {
                    JyoutaiDef WillEnqueue = Jyoutai;
                    WillEnqueue.IsALeft = WillEnqueue.IsBLeft = true;
                    EnqueueSyori(WillEnqueue, 3);
                }
                //船Aと船Cを移動
                if (Jyoutai.IsALeft == false && Jyoutai.IsCLeft == false) {
                    JyoutaiDef WillEnqueue = Jyoutai;
                    WillEnqueue.IsALeft = WillEnqueue.IsCLeft = true;
                    EnqueueSyori(WillEnqueue, 6);
                }
                //船Aと船Dを移動
                if (Jyoutai.IsALeft == false && Jyoutai.IsDLeft == false) {
                    JyoutaiDef WillEnqueue = Jyoutai;
                    WillEnqueue.IsALeft = WillEnqueue.IsDLeft = true;
                    EnqueueSyori(WillEnqueue, 9);
                }
                //船Bと船Cを移動
                if (Jyoutai.IsBLeft == false && Jyoutai.IsCLeft == false) {
                    JyoutaiDef WillEnqueue = Jyoutai;
                    WillEnqueue.IsBLeft = WillEnqueue.IsCLeft = true;
                    EnqueueSyori(WillEnqueue, 6);
                }
                //船Bと船Dを移動
                if (Jyoutai.IsBLeft == false && Jyoutai.IsDLeft == false) {
                    JyoutaiDef WillEnqueue = Jyoutai;
                    WillEnqueue.IsBLeft = WillEnqueue.IsDLeft = true;
                    EnqueueSyori(WillEnqueue, 9);
                }
                //船Cと船Dを移動
                if (Jyoutai.IsCLeft == false && Jyoutai.IsDLeft == false) {
                    JyoutaiDef WillEnqueue = Jyoutai;
                    WillEnqueue.IsCLeft = WillEnqueue.IsDLeft = true;
                    EnqueueSyori(WillEnqueue, 9);
                }
                //船Aを移動
                if (Jyoutai.IsALeft == false) {
                    JyoutaiDef WillEnqueue = Jyoutai;
                    WillEnqueue.IsALeft = true;
                    EnqueueSyori(WillEnqueue, 1);
                }
                //船Bを移動
                if (Jyoutai.IsBLeft == false) {
                    JyoutaiDef WillEnqueue = Jyoutai;
                    WillEnqueue.IsBLeft = true;
                    EnqueueSyori(WillEnqueue, 3);
                }
                //船Cを移動
                if (Jyoutai.IsCLeft == false) {
                    JyoutaiDef WillEnqueue = Jyoutai;
                    WillEnqueue.IsCLeft = true;
                    EnqueueSyori(WillEnqueue, 6);
                }
                //船Dを移動
                if (Jyoutai.IsDLeft == false) {
                    JyoutaiDef WillEnqueue = Jyoutai;
                    WillEnqueue.IsDLeft = true;
                    EnqueueSyori(WillEnqueue, 9);
                }
            }
        }
    }
}

実行結果

省略
解3を発見しました。
レベル 0 船A,船B,船C,船D, 船頭 川川川  合計時間=0
レベル 1 船C,船D, 川川川 船頭 船A,船B, 合計時間=3
レベル 2 船A,船C,船D, 船頭 川川川 船B, 合計時間=4
レベル 3 船A, 川川川 船頭 船B,船C,船D, 合計時間=13
レベル 4 船A,船B, 船頭 川川川 船C,船D, 合計時間=16
レベル 5  川川川 船頭 船A,船B,船C,船D, 合計時間=19
解4を発見しました。
レベル 0 船A,船B,船C,船D, 船頭 川川川  合計時間=0
レベル 1 船C,船D, 川川川 船頭 船A,船B, 合計時間=3
レベル 2 船B,船C,船D, 船頭 川川川 船A, 合計時間=6
レベル 3 船B, 川川川 船頭 船A,船C,船D, 合計時間=15
レベル 4 船A,船B, 船頭 川川川 船C,船D, 合計時間=16
レベル 5  川川川 船頭 船A,船B,船C,船D, 合計時間=19

解説

構造体にメソッドを持たせてます。
構造体は値型なので代入演算だけで、メンバ変数の値型の値をCopyできます。
構造体ではなくクラスにすると、代入演算では、クラスへの参照のコピーになってしまいます。