using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
const int StudentCnt = 14;
struct JyoutaiDef
{
internal int TeacherTelCnt; //Tの受発信回数
internal int StudentCnt1; //受信してない
internal int StudentCnt2; //受信しTに発信不要
internal int StudentCnt2Free; //受信しTに発信不要(行動可)
internal int StudentCnt3; //受信しTに発信必要
internal int StudentCnt4; //受信しTに発信済
internal int Level; //合計分数
internal List<string> LogList; //経路作成のログ
}
static void Main()
{
var sw = System.Diagnostics.Stopwatch.StartNew();
Func<int, char, char, string> wkFunc = (pLevel, pTelFrom, pTelTo) =>
string.Format("{0}分目に、{1}が{2}に発信", pLevel, pTelFrom, pTelTo);
var stk = new Stack<JyoutaiDef>();
JyoutaiDef WillPush;
//最初はTがSに発信するしかない
WillPush.TeacherTelCnt = 1;
WillPush.StudentCnt1 = StudentCnt - 1;
WillPush.StudentCnt2 = 1;
WillPush.StudentCnt2Free = WillPush.StudentCnt2;
WillPush.StudentCnt3 = 0;
WillPush.StudentCnt4 = 0;
WillPush.Level = 1;
WillPush.LogList = new List<string>() { wkFunc(1, 'T', 'S') };
stk.Push(WillPush);
int AnswerLevel = int.MaxValue;
int AnswerTeacherTelCnt = int.MaxValue;
var PoppedLog = new List<JyoutaiDef>();
while (stk.Count > 0) {
JyoutaiDef Popped = stk.Pop();
//メモ化探索
if (PoppedLog.Exists(X =>
{
bool wkBool = X.StudentCnt1 == Popped.StudentCnt1
& X.StudentCnt2 == Popped.StudentCnt2
amp;amp; X.StudentCnt3 == Popped.StudentCnt3
amp;amp; X.StudentCnt4 == Popped.StudentCnt4;
if (wkBool amp;amp; X.Level < Popped.Level) return true;
if (wkBool amp;amp; X.Level == Popped.Level
amp;amp; X.TeacherTelCnt <= Popped.TeacherTelCnt) return true;
return false;
})) continue;
PoppedLog.Add(Popped);
//下限値枝切り
if (AnswerLevel < Popped.Level) continue;
//クリア判定
if (Popped.StudentCnt2 + Popped.StudentCnt4 == StudentCnt) {
if (AnswerLevel > Popped.Level) {
AnswerLevel = Popped.Level;
AnswerTeacherTelCnt = int.MaxValue;
}
if (AnswerTeacherTelCnt <= Popped.TeacherTelCnt) continue;
AnswerTeacherTelCnt = Popped.TeacherTelCnt;
Console.WriteLine("解候補を発見。経過時間={0}", sw.Elapsed);
Console.WriteLine("分数={0}。Tの受発信回数={1}",
Popped.Level, Popped.TeacherTelCnt);
Popped.LogList.ForEach(X => Console.WriteLine(X));
continue;
}
var PushKouhoList = new List<JyoutaiDef>();
JyoutaiDef WillAdd;
//場合1 Tは、何もしない
WillAdd.TeacherTelCnt = Popped.TeacherTelCnt;
WillAdd.StudentCnt1 = Popped.StudentCnt1;
WillAdd.StudentCnt2 = Popped.StudentCnt2;
WillAdd.StudentCnt2Free = Popped.StudentCnt2Free;
WillAdd.StudentCnt3 = Popped.StudentCnt3;
WillAdd.StudentCnt4 = Popped.StudentCnt4;
WillAdd.Level = Popped.Level + 1;
WillAdd.LogList = new List<string>(Popped.LogList);
WillAdd.LogList.Add(string.Format("{0}分目に、Tは何もしない", WillAdd.Level));
PushKouhoList.Add(WillAdd);
//場合2 Tが、Sに発信
if (Popped.StudentCnt1 > 0) {
WillAdd.TeacherTelCnt = Popped.TeacherTelCnt + 1;
WillAdd.StudentCnt1 = Popped.StudentCnt1 - 1;
WillAdd.StudentCnt2 = Popped.StudentCnt2 + 1;
WillAdd.StudentCnt2Free = Popped.StudentCnt2Free;
WillAdd.StudentCnt3 = Popped.StudentCnt3;
WillAdd.StudentCnt4 = Popped.StudentCnt4;
WillAdd.Level = Popped.Level + 1;
WillAdd.LogList = new List<string>(Popped.LogList);
WillAdd.LogList.Add(wkFunc(WillAdd.Level, 'T', 'S'));
PushKouhoList.Add(WillAdd);
}
//場合3 Tが、Sから受信
if (Popped.StudentCnt3 > 0) {
WillAdd.TeacherTelCnt = Popped.TeacherTelCnt + 1;
WillAdd.StudentCnt1 = Popped.StudentCnt1;
WillAdd.StudentCnt2 = Popped.StudentCnt2;
WillAdd.StudentCnt2Free = Popped.StudentCnt2Free;
WillAdd.StudentCnt3 = Popped.StudentCnt3 - 1;
WillAdd.StudentCnt4 = Popped.StudentCnt4 + 1;
WillAdd.Level = Popped.Level + 1;
WillAdd.LogList = new List<string>(Popped.LogList);
WillAdd.LogList.Add(wkFunc(WillAdd.Level, 'S', 'T'));
PushKouhoList.Add(WillAdd);
}
foreach (JyoutaiDef EachJyoutai in PushKouhoList) {
//発信可能なSの数
int FreeStudentCnt = EachJyoutai.StudentCnt2Free
+ EachJyoutai.StudentCnt3;
int LimitI = Math.Min(FreeStudentCnt, EachJyoutai.StudentCnt1);
//SからSへの発信数でループ
for (int I = 0; I <= LimitI; I++) {
int Cnt3 = EachJyoutai.StudentCnt3;
WillPush.TeacherTelCnt = EachJyoutai.TeacherTelCnt;
WillPush.StudentCnt1 = EachJyoutai.StudentCnt1 - I;
//Tへの発信が必要なSのみが、Sに発信
if (I <= Cnt3) {
WillPush.StudentCnt2 = EachJyoutai.StudentCnt2 + I;
WillPush.StudentCnt3 = EachJyoutai.StudentCnt3;
WillPush.StudentCnt4 = EachJyoutai.StudentCnt4;
}
//Tへの発信不要なSも、Sに発信
else {
int Cnt2 = I - Cnt3;
//発信必要なSがA人いたら、発信不要な人がA人増える
//発信不要なSがB人いたら、発信必要な人がB人増える
WillPush.StudentCnt2 = EachJyoutai.StudentCnt2 + Cnt3;
WillPush.StudentCnt3 = EachJyoutai.StudentCnt3 + Cnt2;
WillPush.StudentCnt4 = EachJyoutai.StudentCnt4;
}
WillPush.StudentCnt2Free = WillPush.StudentCnt2;
WillPush.Level = EachJyoutai.Level;
WillPush.LogList = new List<string>(EachJyoutai.LogList);
WillPush.LogList.Add(string.Format(
"{0}分目に、SからSへの発信が{1}回", WillPush.Level, I));
stk.Push(WillPush);
}
}
}
Console.WriteLine("経過時間={0}", sw.Elapsed);
}
}