8-31 川渡り問題2 3匹の狼と小鳥

問題

3匹ずつの狼と小鳥を、向こう岸に渡す。

・いかだに乗れるのは2匹まで
・1匹も乗ってないと動かない
・どちらの岸でも狼が小鳥の数より大きくなると、
  小鳥が食べられて失敗する

渡船者に祝福を : クイズ＆パズルの部屋「Quizzical Days.」

ソース

using System;
using System.Collections.Generic;

class Program
{
    struct JyoutaiDef
    {
        internal int Level;
        internal string MoveLog;
        internal int KotoriLeft;
        internal int OOkamiLeft;
        internal bool IsIkadaLeft;

        internal void Init()
        {
            KotoriLeft = OOkamiLeft = 3;
            IsIkadaLeft = true;
            Logging();
        }

        internal void Logging()
        {
            MoveLog += "レベル" + Level.ToString().PadLeft(2);
            MoveLog += "".PadRight(KotoriLeft, '鳥');
            MoveLog += "".PadRight(OOkamiLeft, '狼');
            MoveLog += IsIkadaLeft ? "筏 川川川" : " 川川川 筏";
            MoveLog += "".PadRight(3 - KotoriLeft, '鳥');
            MoveLog += "".PadRight(3 - OOkamiLeft, '狼');
            MoveLog += Environment.NewLine;
        }
    }

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

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

        int AnswerLevel = int.MaxValue;
        while (que.Count != 0) {
            Jyoutai = que.Dequeue();
            if (++Jyoutai.Level > AnswerLevel) continue;

            if (Jyoutai.IsIkadaLeft == false
             && Jyoutai.KotoriLeft == 0
             && Jyoutai.OOkamiLeft == 0) {
                AnswerLevel = Jyoutai.Level;
                Console.WriteLine("Answer");
                Console.WriteLine(Jyoutai.MoveLog);
                continue;
            }

            JyoutaiDef WillEnqueue;
            if (Jyoutai.IsIkadaLeft) {
                if (Jyoutai.KotoriLeft >= 2) {
                    WillEnqueue = Jyoutai;
                    WillEnqueue.KotoriLeft -= 2; WillEnqueue.IsIkadaLeft = false;
                    WillEnqueue.Logging();
                    if (IsValid(WillEnqueue)) que.Enqueue(WillEnqueue);
                }
                if (Jyoutai.OOkamiLeft >= 2) {
                    WillEnqueue = Jyoutai;
                    WillEnqueue.OOkamiLeft -= 2; WillEnqueue.IsIkadaLeft = false;
                    WillEnqueue.Logging();
                    if (IsValid(WillEnqueue)) que.Enqueue(WillEnqueue);
                }
                if (Jyoutai.KotoriLeft >= 1) {
                    WillEnqueue = Jyoutai;
                    WillEnqueue.KotoriLeft--; WillEnqueue.IsIkadaLeft = false;
                    WillEnqueue.Logging();
                    if (IsValid(WillEnqueue)) que.Enqueue(WillEnqueue);
                }
                if (Jyoutai.OOkamiLeft >= 1) {
                    WillEnqueue = Jyoutai;
                    WillEnqueue.OOkamiLeft--; WillEnqueue.IsIkadaLeft = false;
                    WillEnqueue.Logging();
                    if (IsValid(WillEnqueue)) que.Enqueue(WillEnqueue);
                }
                if (Jyoutai.KotoriLeft >= 1 && Jyoutai.OOkamiLeft >= 1) {
                    WillEnqueue = Jyoutai;
                    WillEnqueue.KotoriLeft--;
                    WillEnqueue.OOkamiLeft--; WillEnqueue.IsIkadaLeft = false;
                    WillEnqueue.Logging();
                    if (IsValid(WillEnqueue)) que.Enqueue(WillEnqueue);
                }
            }

            else {
                if ((3 - Jyoutai.KotoriLeft) >= 2) {
                    WillEnqueue = Jyoutai;
                    WillEnqueue.KotoriLeft += 2; WillEnqueue.IsIkadaLeft = true;
                    WillEnqueue.Logging();
                    if (IsValid(WillEnqueue)) que.Enqueue(WillEnqueue);
                }
                if ((3 - Jyoutai.OOkamiLeft) >= 2) {
                    WillEnqueue = Jyoutai;
                    WillEnqueue.OOkamiLeft += 2; WillEnqueue.IsIkadaLeft = true;
                    WillEnqueue.Logging();
                    if (IsValid(WillEnqueue)) que.Enqueue(WillEnqueue);
                }
                if ((3 - Jyoutai.KotoriLeft) >= 1) {
                    WillEnqueue = Jyoutai;
                    WillEnqueue.KotoriLeft++; WillEnqueue.IsIkadaLeft = true;
                    WillEnqueue.Logging();
                    if (IsValid(WillEnqueue)) que.Enqueue(WillEnqueue);
                }
                if ((3 - Jyoutai.OOkamiLeft) >= 1) {
                    WillEnqueue = Jyoutai;
                    WillEnqueue.OOkamiLeft++; WillEnqueue.IsIkadaLeft = true;
                    WillEnqueue.Logging();
                    if (IsValid(WillEnqueue)) que.Enqueue(WillEnqueue);
                }
                if ((3 - Jyoutai.KotoriLeft) >= 1 && (3 - Jyoutai.OOkamiLeft) >= 1) {
                    WillEnqueue = Jyoutai;
                    WillEnqueue.KotoriLeft++;
                    WillEnqueue.OOkamiLeft++; WillEnqueue.IsIkadaLeft = true;
                    WillEnqueue.Logging();
                    if (IsValid(WillEnqueue)) que.Enqueue(WillEnqueue);
                }
            }
        }
    }
    static bool IsValid(JyoutaiDef pJyoutai)
    {
        if (pJyoutai.KotoriLeft >= 1 &&
            pJyoutai.KotoriLeft < pJyoutai.OOkamiLeft) return false;
        if ((3 - pJyoutai.KotoriLeft) >= 1 &&
            (3 - pJyoutai.KotoriLeft) < (3 - pJyoutai.OOkamiLeft)) return false;
        return true;
    }
}

実行結果

Answer
レベル 0鳥鳥鳥狼狼狼筏 川川川
レベル 1鳥鳥鳥狼 川川川 筏狼狼
レベル 2鳥鳥鳥狼狼筏 川川川狼
レベル 3鳥鳥鳥 川川川 筏狼狼狼
レベル 4鳥鳥鳥狼筏 川川川狼狼
レベル 5鳥狼 川川川 筏鳥鳥狼狼
レベル 6鳥鳥狼狼筏 川川川鳥狼
レベル 7狼狼 川川川 筏鳥鳥鳥狼
レベル 8狼狼狼筏 川川川鳥鳥鳥
レベル 9狼 川川川 筏鳥鳥鳥狼狼
レベル10鳥狼筏 川川川鳥鳥狼狼
レベル11 川川川 筏鳥鳥鳥狼狼狼

Answer
レベル 0鳥鳥鳥狼狼狼筏 川川川
レベル 1鳥鳥鳥狼 川川川 筏狼狼
レベル 2鳥鳥鳥狼狼筏 川川川狼
レベル 3鳥鳥鳥 川川川 筏狼狼狼
レベル 4鳥鳥鳥狼筏 川川川狼狼
レベル 5鳥狼 川川川 筏鳥鳥狼狼
レベル 6鳥鳥狼狼筏 川川川鳥狼
レベル 7狼狼 川川川 筏鳥鳥鳥狼
レベル 8狼狼狼筏 川川川鳥鳥鳥
レベル 9狼 川川川 筏鳥鳥鳥狼狼
レベル10狼狼筏 川川川鳥鳥鳥狼
レベル11 川川川 筏鳥鳥鳥狼狼狼

Answer
レベル 0鳥鳥鳥狼狼狼筏 川川川
レベル 1鳥鳥狼狼 川川川 筏鳥狼
レベル 2鳥鳥鳥狼狼筏 川川川狼
レベル 3鳥鳥鳥 川川川 筏狼狼狼
レベル 4鳥鳥鳥狼筏 川川川狼狼
レベル 5鳥狼 川川川 筏鳥鳥狼狼
レベル 6鳥鳥狼狼筏 川川川鳥狼
レベル 7狼狼 川川川 筏鳥鳥鳥狼
レベル 8狼狼狼筏 川川川鳥鳥鳥
レベル 9狼 川川川 筏鳥鳥鳥狼狼
レベル10鳥狼筏 川川川鳥鳥狼狼
レベル11 川川川 筏鳥鳥鳥狼狼狼

Answer
レベル 0鳥鳥鳥狼狼狼筏 川川川
レベル 1鳥鳥狼狼 川川川 筏鳥狼
レベル 2鳥鳥鳥狼狼筏 川川川狼
レベル 3鳥鳥鳥 川川川 筏狼狼狼
レベル 4鳥鳥鳥狼筏 川川川狼狼
レベル 5鳥狼 川川川 筏鳥鳥狼狼
レベル 6鳥鳥狼狼筏 川川川鳥狼
レベル 7狼狼 川川川 筏鳥鳥鳥狼
レベル 8狼狼狼筏 川川川鳥鳥鳥
レベル 9狼 川川川 筏鳥鳥鳥狼狼
レベル10狼狼筏 川川川鳥鳥鳥狼
レベル11 川川川 筏鳥鳥鳥狼狼狼

解説

Queueジェネリックは強力ですねぇ