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

問題

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

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

ソース

#include <string>
#include <queue>
#include <Windows.h>
#include <iostream>

class JyoutaiDef{
public:
    int Level;
    std::string MoveLog;
    int KotoriLeft;
    int OOkamiLeft;
    bool IsIkadaLeft;

    JyoutaiDef()
        : Level(0),IsIkadaLeft(true)
    {
        KotoriLeft = OOkamiLeft = 3;
        Logging();
    }

    void Logging()
    {
        MoveLog += "レベル";
        char wk[99]; wsprintf(wk,"%2d",Level);
        MoveLog += wk;
        for(int I=1;I<= KotoriLeft;I++) MoveLog +="鳥";
        for(int I=1;I<= OOkamiLeft;I++) MoveLog +="狼";
        MoveLog += IsIkadaLeft ? "筏 川川川" : " 川川川 筏";
        for(int I=1;I<= 3-KotoriLeft;I++) MoveLog +="鳥";
        for(int I=1;I<= 3-OOkamiLeft;I++) MoveLog +="狼";
        MoveLog +="\n";
    }
};

bool IsValid(JyoutaiDef p);

void main()
{
    JyoutaiDef Jyoutai;
    std::queue<JyoutaiDef> que;
    que.push(Jyoutai);

    int AnswerLevel = INT_MAX;
    while(que.empty() == false){
        Jyoutai =  que.front();que.pop();
        if (++Jyoutai.Level > AnswerLevel) continue;

        if (Jyoutai.IsIkadaLeft == false
         && Jyoutai.KotoriLeft == 0
         && Jyoutai.OOkamiLeft == 0) {
             AnswerLevel = Jyoutai.Level;
             std::cout << "Answer" << std::endl;
             std::cout << Jyoutai.MoveLog << std::endl;
             continue;
        }

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

        else {
            if ((3 - Jyoutai.KotoriLeft) >= 2) {
                Saved = Jyoutai;
                Saved.KotoriLeft += 2; Saved.IsIkadaLeft = true;
                Saved.Logging();
                if (IsValid(Saved)) que.push(Saved);
            }
            if ((3 - Jyoutai.OOkamiLeft) >= 2) {
                Saved = Jyoutai;
                Saved.OOkamiLeft += 2; Saved.IsIkadaLeft = true;
                Saved.Logging();
                if (IsValid(Saved)) que.push(Saved);
            }
            if ((3 - Jyoutai.KotoriLeft) >= 1) {
                Saved = Jyoutai;
                Saved.KotoriLeft++; Saved.IsIkadaLeft = true;
                Saved.Logging();
                if (IsValid(Saved)) que.push(Saved);
            }
            if ((3 - Jyoutai.OOkamiLeft) >= 1) {
                Saved = Jyoutai;
                Saved.OOkamiLeft++; Saved.IsIkadaLeft = true;
                Saved.Logging();
                if (IsValid(Saved)) que.push(Saved);
            }
            if ((3 - Jyoutai.KotoriLeft) >= 1 && (3 - Jyoutai.OOkamiLeft) >= 1) {
                Saved = Jyoutai;
                Saved.KotoriLeft++;
                Saved.OOkamiLeft++; Saved.IsIkadaLeft = true;
                Saved.Logging();
                if (IsValid(Saved)) que.push(Saved);
            }
        }
    }
}

bool IsValid(JyoutaiDef p)
{
    if (p.KotoriLeft >= 1 && p.KotoriLeft < p.OOkamiLeft) return false;
    if ((3 - p.KotoriLeft) >= 1 && (3 - p.KotoriLeft) < (3 - p.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 川川川 筏鳥鳥鳥狼狼狼

解説

幅優先探索で、ひたすら場合分けをして探索してます。