トラ・ライオン・ヒョウの3組の親子が、舟で川を渡ろうとしている。 舟は1艘(そう)しかないが、1度に2匹まで乗ることができ、 またどの動物も舟を漕(こ)ぐことが可能である。 ただし、親子同士でない成獣(親)と幼獣(子)が同じ場所におり、 かつその子の親が近くにいない場合、子は食べられてしまう。 さて、全員が無事に川を渡り切るにはどうすればよいだろうか? 猛獣親子の川渡り : クイズ＆パズルの部屋「Quizzical Days.」
using System;
using System.Collections.Generic;
class Program
{
struct JyoutaiDef
{
internal int Level;
internal bool IsToraOyaLeft;
internal bool IsToraKoLeft;
internal bool IsLionOyaLeft;
internal bool IsLionKoLeft;
internal bool IsHyouOyaLeft;
internal bool IsHyouKoLeft;
internal bool IsIkadaLeft;
internal List<string> LogList;
internal void Init()
{
Level = 0;
IsToraOyaLeft = IsToraKoLeft = true;
IsLionOyaLeft = IsLionKoLeft = true;
IsHyouOyaLeft = IsHyouKoLeft = true;
IsIkadaLeft = true;
LogList = new List<string>();
AddOneLog();
}
internal void MakeKishiInfo(bool pIsLeftInfo, System.Text.StringBuilder pSb)
{
if (pIsLeftInfo == IsToraOyaLeft) pSb.Append("親トラ,");
if (pIsLeftInfo == IsToraKoLeft) pSb.Append("子トラ,");
if (pIsLeftInfo == IsLionOyaLeft) pSb.Append("親ライオン,");
if (pIsLeftInfo == IsLionKoLeft) pSb.Append("子ライオン,");
if (pIsLeftInfo == IsHyouOyaLeft) pSb.Append("親ヒョウ,");
if (pIsLeftInfo == IsHyouKoLeft) pSb.Append("子ヒョウ,");
}
internal bool AddOneLog()
{
var sb = new System.Text.StringBuilder();
MakeKishiInfo(true, sb);
sb.Append(IsIkadaLeft ? " 筏 川川川 " : " 川川川 筏 ");
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}", I, LogList[I]);
}
internal bool IsValid()
{
if (IsToraOyaLeft != IsToraKoLeft &&
(IsToraKoLeft == IsLionOyaLeft || IsToraKoLeft == IsHyouOyaLeft)) return false;
if (IsLionOyaLeft != IsLionKoLeft &&
(IsLionKoLeft == IsToraOyaLeft || IsLionKoLeft == IsHyouOyaLeft)) return false;
if (IsHyouOyaLeft != IsHyouKoLeft &&
(IsHyouKoLeft == IsToraOyaLeft || IsHyouKoLeft == IsLionOyaLeft)) return false;
return true;
}
}
static void Main()
{
var Jyoutai = new JyoutaiDef();
Jyoutai.Init();
var que = new Queue<JyoutaiDef>();
que.Enqueue(Jyoutai);
int AnswerLevel = int.MaxValue;
int AnswerCnt = 0;
while (que.Count != 0) {
Jyoutai = que.Dequeue();
//Jyoutai.PrintLog();
if (++Jyoutai.Level > AnswerLevel) continue;
if (Jyoutai.IsToraOyaLeft == false && Jyoutai.IsToraKoLeft == false
&& Jyoutai.IsLionOyaLeft == false && Jyoutai.IsLionKoLeft == false
&& Jyoutai.IsHyouOyaLeft == false && Jyoutai.IsHyouKoLeft == false
&& Jyoutai.IsIkadaLeft == false) {
Console.WriteLine("解{0}を発見しました。", ++AnswerCnt);
Jyoutai.PrintLog();
AnswerLevel = Jyoutai.Level;
continue;
}
Action<JyoutaiDef> EnqueueSyori = (pWillEnqueue) =>
{
pWillEnqueue.LogList = new List<string>(Jyoutai.LogList);
pWillEnqueue.IsIkadaLeft = !Jyoutai.IsIkadaLeft;
if (pWillEnqueue.AddOneLog() && pWillEnqueue.IsValid())
que.Enqueue(pWillEnqueue);
};
if (Jyoutai.IsIkadaLeft) {
//親トラと親ライオンで移動
if (Jyoutai.IsToraOyaLeft && Jyoutai.IsLionOyaLeft) {
JyoutaiDef WillEnqueue = Jyoutai;
WillEnqueue.IsToraOyaLeft = WillEnqueue.IsLionOyaLeft = false;
EnqueueSyori(WillEnqueue);
}
//親トラと親ヒョウで移動
if (Jyoutai.IsToraOyaLeft && Jyoutai.IsHyouOyaLeft) {
JyoutaiDef WillEnqueue = Jyoutai;
WillEnqueue.IsToraOyaLeft = WillEnqueue.IsHyouOyaLeft = false;
EnqueueSyori(WillEnqueue);
}
//親ライオンと親ヒョウで移動
if (Jyoutai.IsLionOyaLeft && Jyoutai.IsHyouOyaLeft) {
JyoutaiDef WillEnqueue = Jyoutai;
WillEnqueue.IsLionOyaLeft = WillEnqueue.IsHyouOyaLeft = false;
EnqueueSyori(WillEnqueue);
}
//親トラで移動
if (Jyoutai.IsToraOyaLeft) {
JyoutaiDef WillEnqueue = Jyoutai;
WillEnqueue.IsToraOyaLeft = false;
EnqueueSyori(WillEnqueue);
}
//親ライオンで移動
if (Jyoutai.IsLionOyaLeft) {
JyoutaiDef WillEnqueue = Jyoutai;
WillEnqueue.IsLionOyaLeft = false;
EnqueueSyori(WillEnqueue);
}
//親ヒョウで移動
if (Jyoutai.IsHyouOyaLeft) {
JyoutaiDef WillEnqueue = Jyoutai;
WillEnqueue.IsHyouOyaLeft = false;
EnqueueSyori(WillEnqueue);
}
//親トラと子トラで移動
if (Jyoutai.IsToraOyaLeft && Jyoutai.IsToraKoLeft) {
JyoutaiDef WillEnqueue = Jyoutai;
WillEnqueue.IsToraOyaLeft = WillEnqueue.IsToraKoLeft = false;
EnqueueSyori(WillEnqueue);
}
//親ライオンと子ライオンで移動
if (Jyoutai.IsLionOyaLeft && Jyoutai.IsLionKoLeft) {
JyoutaiDef WillEnqueue = Jyoutai;
WillEnqueue.IsLionOyaLeft = WillEnqueue.IsLionKoLeft = false;
EnqueueSyori(WillEnqueue);
}
//親ヒョウと子ヒョウで移動
if (Jyoutai.IsHyouOyaLeft && Jyoutai.IsHyouKoLeft) {
JyoutaiDef WillEnqueue = Jyoutai;
WillEnqueue.IsHyouOyaLeft = WillEnqueue.IsHyouKoLeft = false;
EnqueueSyori(WillEnqueue);
}
//子トラと子ライオンで移動
if (Jyoutai.IsToraKoLeft && Jyoutai.IsLionKoLeft) {
JyoutaiDef WillEnqueue = Jyoutai;
WillEnqueue.IsToraKoLeft = WillEnqueue.IsLionKoLeft = false;
EnqueueSyori(WillEnqueue);
}
//子トラと子ヒョウで移動
if (Jyoutai.IsToraKoLeft && Jyoutai.IsHyouKoLeft) {
JyoutaiDef WillEnqueue = Jyoutai;
WillEnqueue.IsToraKoLeft = WillEnqueue.IsHyouKoLeft = false;
EnqueueSyori(WillEnqueue);
}
//子ライオンと子ヒョウで移動
if (Jyoutai.IsLionKoLeft && Jyoutai.IsHyouKoLeft) {
JyoutaiDef WillEnqueue = Jyoutai;
WillEnqueue.IsLionKoLeft = WillEnqueue.IsHyouKoLeft = false;
EnqueueSyori(WillEnqueue);
}
//子トラで移動
if (Jyoutai.IsToraKoLeft) {
JyoutaiDef WillEnqueue = Jyoutai;
WillEnqueue.IsToraKoLeft = false;
EnqueueSyori(WillEnqueue);
}
//子ライオンで移動
if (Jyoutai.IsLionKoLeft) {
JyoutaiDef WillEnqueue = Jyoutai;
WillEnqueue.IsLionKoLeft = false;
EnqueueSyori(WillEnqueue);
}
//子ヒョウで移動
if (Jyoutai.IsHyouKoLeft) {
JyoutaiDef WillEnqueue = Jyoutai;
WillEnqueue.IsHyouKoLeft = false;
EnqueueSyori(WillEnqueue);
}
}
else {
//親トラと親ライオンで移動
if (Jyoutai.IsToraOyaLeft == false && Jyoutai.IsLionOyaLeft == false) {
JyoutaiDef WillEnqueue = Jyoutai;
WillEnqueue.IsToraOyaLeft = WillEnqueue.IsLionOyaLeft = true;
EnqueueSyori(WillEnqueue);
}
//親トラと親ヒョウで移動
if (Jyoutai.IsToraOyaLeft == false && Jyoutai.IsHyouOyaLeft == false) {
JyoutaiDef WillEnqueue = Jyoutai;
WillEnqueue.IsToraOyaLeft = WillEnqueue.IsHyouOyaLeft = true;
EnqueueSyori(WillEnqueue);
}
//親ライオンと親ヒョウで移動
if (Jyoutai.IsLionOyaLeft == false && Jyoutai.IsHyouOyaLeft == false) {
JyoutaiDef WillEnqueue = Jyoutai;
WillEnqueue.IsLionOyaLeft = WillEnqueue.IsHyouOyaLeft = true;
EnqueueSyori(WillEnqueue);
}
//親トラで移動
if (Jyoutai.IsToraOyaLeft == false) {
JyoutaiDef WillEnqueue = Jyoutai;
WillEnqueue.IsToraOyaLeft = true;
EnqueueSyori(WillEnqueue);
}
//親ライオンで移動
if (Jyoutai.IsLionOyaLeft == false) {
JyoutaiDef WillEnqueue = Jyoutai;
WillEnqueue.IsLionOyaLeft = true;
EnqueueSyori(WillEnqueue);
}
//親ヒョウで移動
if (Jyoutai.IsHyouOyaLeft == false) {
JyoutaiDef WillEnqueue = Jyoutai;
WillEnqueue.IsHyouOyaLeft = true;
EnqueueSyori(WillEnqueue);
}
//親トラと子トラで移動
if (Jyoutai.IsToraOyaLeft == false && Jyoutai.IsToraKoLeft == false) {
JyoutaiDef WillEnqueue = Jyoutai;
WillEnqueue.IsToraOyaLeft = WillEnqueue.IsToraKoLeft = true;
EnqueueSyori(WillEnqueue);
}
//親ライオンと子ライオンで移動
if (Jyoutai.IsLionOyaLeft == false && Jyoutai.IsLionKoLeft == false) {
JyoutaiDef WillEnqueue = Jyoutai;
WillEnqueue.IsLionOyaLeft = WillEnqueue.IsLionKoLeft = true;
EnqueueSyori(WillEnqueue);
}
//親ヒョウと子ヒョウで移動
if (Jyoutai.IsHyouOyaLeft == false && Jyoutai.IsHyouKoLeft == false) {
JyoutaiDef WillEnqueue = Jyoutai;
WillEnqueue.IsHyouOyaLeft = WillEnqueue.IsHyouKoLeft = true;
EnqueueSyori(WillEnqueue);
}
//子トラと子ライオンで移動
if (Jyoutai.IsToraKoLeft == false && Jyoutai.IsLionKoLeft == false) {
JyoutaiDef WillEnqueue = Jyoutai;
WillEnqueue.IsToraKoLeft = WillEnqueue.IsLionKoLeft = true;
EnqueueSyori(WillEnqueue);
}
//子トラと子ヒョウで移動
if (Jyoutai.IsToraKoLeft == false && Jyoutai.IsHyouKoLeft == false) {
JyoutaiDef WillEnqueue = Jyoutai;
WillEnqueue.IsToraKoLeft = WillEnqueue.IsHyouKoLeft = true;
EnqueueSyori(WillEnqueue);
}
//子ライオンと子ヒョウで移動
if (Jyoutai.IsLionKoLeft == false && Jyoutai.IsHyouKoLeft == false) {
JyoutaiDef WillEnqueue = Jyoutai;
WillEnqueue.IsLionKoLeft = WillEnqueue.IsHyouKoLeft = true;
EnqueueSyori(WillEnqueue);
}
//子トラで移動
if (Jyoutai.IsToraKoLeft == false) {
JyoutaiDef WillEnqueue = Jyoutai;
WillEnqueue.IsToraKoLeft = true;
EnqueueSyori(WillEnqueue);
}
//子ライオンで移動
if (Jyoutai.IsLionKoLeft == false) {
JyoutaiDef WillEnqueue = Jyoutai;
WillEnqueue.IsLionKoLeft = true;
EnqueueSyori(WillEnqueue);
}
//子ヒョウで移動
if (Jyoutai.IsHyouKoLeft == false) {
JyoutaiDef WillEnqueue = Jyoutai;
WillEnqueue.IsHyouKoLeft = true;
EnqueueSyori(WillEnqueue);
}
}
}
}
}
省略 解486を発見しました。 レベル 0 親トラ,子トラ,親ライオン,子ライオン,親ヒョウ,子ヒョウ, 筏 川川川 レベル 1 親トラ,子トラ,親ライオン,親ヒョウ, 川川川 筏 子ライオン,子ヒョウ, レベル 2 親トラ,子トラ,親ライオン,親ヒョウ,子ヒョウ, 筏 川川川 子ライオン, レベル 3 親トラ,親ライオン,親ヒョウ, 川川川 筏 子トラ,子ライオン,子ヒョウ, レベル 4 親トラ,親ライオン,親ヒョウ,子ヒョウ, 筏 川川川 子トラ,子ライオン, レベル 5 親ヒョウ,子ヒョウ, 川川川 筏 親トラ,子トラ,親ライオン,子ライオン, レベル 6 親ライオン,子ライオン,親ヒョウ,子ヒョウ, 筏 川川川 親トラ,子トラ, レベル 7 子ライオン,子ヒョウ, 川川川 筏 親トラ,子トラ,親ライオン,親ヒョウ, レベル 8 子トラ,子ライオン,子ヒョウ, 筏 川川川 親トラ,親ライオン,親ヒョウ, レベル 9 子トラ, 川川川 筏 親トラ,親ライオン,子ライオン,親ヒョウ,子ヒョウ, レベル10 子トラ,子ヒョウ, 筏 川川川 親トラ,親ライオン,子ライオン,親ヒョウ, レベル11 川川川 筏 親トラ,子トラ,親ライオン,子ライオン,親ヒョウ,子ヒョウ,
幅優先探索で解いてます。