トップページに戻る
次のC#のサンプルへ
前のC#のサンプルへ
8-35 川渡り問題6 暗闇恐怖症
問題
4人の人間が、闇夜の中、細い吊り橋を渡ろうとしている。
橋は古く、2人分までの重さにしか耐えることができない。
また、暗く危険なので、橋を渡る時にはたいまつが必要である。
さて、Aは橋を渡るのに1分かかり、
同様に、Bは2分、Cは5分、Dは8分かかる。
ただし、たいまつは1本しかないので、2人が一緒に橋を渡る際には、
より遅い方の人に合わせて渡らなければならない。
さて、たいまつの火が消えるまであと15分しかない。
この条件で、15分以内に全員が橋を渡り切ることができるだろうか?
暗闇恐怖症 : クイズ＆パズルの部屋「Quizzical Days.」
ソース
using System;
using System.Collections.Generic;
class Program
{
struct JyoutaiDef
{
internal bool IsALeft;
internal bool IsBLeft;
internal bool IsCLeft;
internal bool IsDLeft;
internal bool IsTaimatuLeft;
internal List<string> LogList;
internal List<int> TimeRunSumList;
internal void Init()
{
IsALeft = IsBLeft = IsCLeft = IsDLeft = true;
IsTaimatuLeft = 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(IsTaimatuLeft ? " たいまつ 吊り橋 " : " 吊り橋 たいまつ ");
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} {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 = 15;
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.IsTaimatuLeft == 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.IsTaimatuLeft = !Jyoutai.IsTaimatuLeft;
if (pWillEnqueue.AddOneLog()) que.Enqueue(pWillEnqueue);
};
if (Jyoutai.IsTaimatuLeft) {
//AとBを移動
if (Jyoutai.IsALeft && Jyoutai.IsBLeft) {
JyoutaiDef WillEnqueue = Jyoutai;
WillEnqueue.IsALeft = WillEnqueue.IsBLeft = false;
EnqueueSyori(WillEnqueue, 2);
}
//AとCを移動
if (Jyoutai.IsALeft && Jyoutai.IsCLeft) {
JyoutaiDef WillEnqueue = Jyoutai;
WillEnqueue.IsALeft = WillEnqueue.IsCLeft = false;
EnqueueSyori(WillEnqueue, 5);
}
//AとDを移動
if (Jyoutai.IsALeft && Jyoutai.IsDLeft) {
JyoutaiDef WillEnqueue = Jyoutai;
WillEnqueue.IsALeft = WillEnqueue.IsDLeft = false;
EnqueueSyori(WillEnqueue, 8);
}
//BとCを移動
if (Jyoutai.IsBLeft && Jyoutai.IsCLeft) {
JyoutaiDef WillEnqueue = Jyoutai;
WillEnqueue.IsBLeft = WillEnqueue.IsCLeft = false;
EnqueueSyori(WillEnqueue, 5);
}
//BとDを移動
if (Jyoutai.IsBLeft && Jyoutai.IsDLeft) {
JyoutaiDef WillEnqueue = Jyoutai;
WillEnqueue.IsBLeft = WillEnqueue.IsDLeft = false;
EnqueueSyori(WillEnqueue, 8);
}
//CとDを移動
if (Jyoutai.IsCLeft && Jyoutai.IsDLeft) {
JyoutaiDef WillEnqueue = Jyoutai;
WillEnqueue.IsCLeft = WillEnqueue.IsDLeft = false;
EnqueueSyori(WillEnqueue, 8);
}
//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, 2);
}
//Cを移動
if (Jyoutai.IsCLeft) {
JyoutaiDef WillEnqueue = Jyoutai;
WillEnqueue.IsCLeft = false;
EnqueueSyori(WillEnqueue, 5);
}
//Dを移動
if (Jyoutai.IsDLeft) {
JyoutaiDef WillEnqueue = Jyoutai;
WillEnqueue.IsDLeft = false;
EnqueueSyori(WillEnqueue, 8);
}
}
else {
//AとBを移動
if (Jyoutai.IsALeft == false && Jyoutai.IsBLeft == false) {
JyoutaiDef WillEnqueue = Jyoutai;
WillEnqueue.IsALeft = WillEnqueue.IsBLeft = true;
EnqueueSyori(WillEnqueue, 2);
}
//AとCを移動
if (Jyoutai.IsALeft == false && Jyoutai.IsCLeft == false) {
JyoutaiDef WillEnqueue = Jyoutai;
WillEnqueue.IsALeft = WillEnqueue.IsCLeft = true;
EnqueueSyori(WillEnqueue, 5);
}
//AとDを移動
if (Jyoutai.IsALeft == false && Jyoutai.IsDLeft == false) {
JyoutaiDef WillEnqueue = Jyoutai;
WillEnqueue.IsALeft = WillEnqueue.IsDLeft = true;
EnqueueSyori(WillEnqueue, 8);
}
//BとCを移動
if (Jyoutai.IsBLeft == false && Jyoutai.IsCLeft == false) {
JyoutaiDef WillEnqueue = Jyoutai;
WillEnqueue.IsBLeft = WillEnqueue.IsCLeft = true;
EnqueueSyori(WillEnqueue, 5);
}
//BとDを移動
if (Jyoutai.IsBLeft == false && Jyoutai.IsDLeft == false) {
JyoutaiDef WillEnqueue = Jyoutai;
WillEnqueue.IsBLeft = WillEnqueue.IsDLeft = true;
EnqueueSyori(WillEnqueue, 8);
}
//CとDを移動
if (Jyoutai.IsCLeft == false && Jyoutai.IsDLeft == false) {
JyoutaiDef WillEnqueue = Jyoutai;
WillEnqueue.IsCLeft = WillEnqueue.IsDLeft = true;
EnqueueSyori(WillEnqueue, 8);
}
//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, 2);
}
//Cを移動
if (Jyoutai.IsCLeft == false) {
JyoutaiDef WillEnqueue = Jyoutai;
WillEnqueue.IsCLeft = true;
EnqueueSyori(WillEnqueue, 5);
}
//Dを移動
if (Jyoutai.IsDLeft == false) {
JyoutaiDef WillEnqueue = Jyoutai;
WillEnqueue.IsDLeft = true;
EnqueueSyori(WillEnqueue, 8);
}
}
}
}
}
実行結果
解1を発見しました。
レベル0 A,B,C,D, たいまつ 吊り橋 合計時間=0
レベル1 C,D, 吊り橋 たいまつ A,B, 合計時間=2
レベル2 A,C,D, たいまつ 吊り橋 B, 合計時間=3
レベル3 A, 吊り橋 たいまつ B,C,D, 合計時間=11
レベル4 A,B, たいまつ 吊り橋 C,D, 合計時間=13
レベル5 吊り橋 たいまつ A,B,C,D, 合計時間=15
解2を発見しました。
レベル0 A,B,C,D, たいまつ 吊り橋 合計時間=0
レベル1 C,D, 吊り橋 たいまつ A,B, 合計時間=2
レベル2 B,C,D, たいまつ 吊り橋 A, 合計時間=4
レベル3 B, 吊り橋 たいまつ A,C,D, 合計時間=12
レベル4 A,B, たいまつ 吊り橋 C,D, 合計時間=13
レベル5 吊り橋 たいまつ A,B,C,D, 合計時間=15
解説
合計時間が15分を超えた時点で枝切りできるようにしてます。