using System;
using System.Collections.Generic;
class Program
{
const int UB = 5 - 1;
struct PointDef
{
internal int X;
internal int Y;
}
struct JyoutaiDef
{
internal int Level;
internal bool[,] BanArr;
internal PointDef CurrPos;
internal List<bool[,]> Log;
}
static void Main()
{
var Stk = new Stack<JyoutaiDef>();
JyoutaiDef WillPush;
WillPush.Level = 0;
WillPush.BanArr = InitBan();
WillPush.CurrPos = new PointDef() { X = -1, Y = -1 };
WillPush.Log = new List<bool[,]>() { WillPush.BanArr };
Stk.Push(WillPush);
int AnswerLevel = int.MaxValue;
while (Stk.Count > 0) {
JyoutaiDef Popped = Stk.Pop();
//クリア判定
if (IsClear(Popped.BanArr)) {
if (Popped.Level < AnswerLevel) {
AnswerLevel = Popped.Level;
Console.WriteLine("{0}手の解候補を発見", Popped.Level);
for (int I = 0; I <= Popped.Log.Count - 1; I++) {
Console.WriteLine("レベル{0}", I);
PrintBan(Popped.Log[I]);
}
}
continue;
}
//下限値枝切り
if (AnswerLevel <= Popped.Level) continue;
for (int LoopX = 0; LoopX <= UB; LoopX++) {
for (int LoopY = 0; LoopY <= UB; LoopY++) {
//対称解の除外で、最初はAからジャンプ
if (Popped.CurrPos.X == -1)
if (LoopX != 0 || LoopY != 0) continue;
if (Popped.BanArr[LoopX, LoopY] == false) continue;
JumpedInfoDef[] JumpedInfoArr =
DeriveJumpedInfoArr(Popped.BanArr, LoopX, LoopY);
foreach (JumpedInfoDef EachJumoedInfo in JumpedInfoArr) {
if (Popped.CurrPos.X != LoopX || Popped.CurrPos.Y != LoopY)
WillPush.Level = Popped.Level + 1;
else WillPush.Level = Popped.Level;
WillPush.BanArr = EachJumoedInfo.BanArr;
WillPush.CurrPos = EachJumoedInfo.NewCurrPos;
WillPush.Log = new List<bool[,]>(Popped.Log) { WillPush.BanArr };
Stk.Push(WillPush);
}
}
}
}
}
//盤の初期状態を返す
static bool[,] InitBan()
{
bool[,] WillReturn = new bool[UB + 1, UB + 1];
WillReturn[0, 0] = WillReturn[2, 0] = WillReturn[4, 0] = true;
WillReturn[1, 1] = WillReturn[3, 1] = true;
WillReturn[0, 2] = WillReturn[4, 2] = true;
WillReturn[1, 3] = WillReturn[3, 3] = true;
WillReturn[0, 4] = WillReturn[2, 4] = WillReturn[4, 4] = true;
return WillReturn;
}
//クリア判定
static bool IsClear(bool[,] pBanArr)
{
if (pBanArr[2, 2] == false) return false;
for (int LoopX = 0; LoopX <= UB; LoopX++) {
for (int LoopY = 0; LoopY <= UB; LoopY++) {
if (LoopX == 2 && LoopY == 2) continue;
if (pBanArr[LoopX, LoopY]) return false;
}
}
return true;
}
//ジャンプ後の盤情報
struct JumpedInfoDef
{
internal bool[,] BanArr;
internal PointDef NewCurrPos;
}
//カエルのジャンプ後の盤情報の配列を返す
static JumpedInfoDef[] DeriveJumpedInfoArr(bool[,] pBanArr, int pFromX, int pFromY)
{
var WillReturn = new List<JumpedInfoDef>();
Action<int, int> JumpAct = (pHeniX, pHeniY) =>
{
if (CanJump(pBanArr, pFromX, pFromY, pHeniX, pHeniY) == false)
return;
bool[,] wkArr = (bool[,])pBanArr.Clone();
wkArr[pFromX, pFromY] = false;
wkArr[pFromX + pHeniX, pFromY + pHeniY] = false;
wkArr[pFromX + pHeniX * 2, pFromY + pHeniY * 2] = true;
JumpedInfoDef WillAdd;
WillAdd.BanArr = wkArr;
WillAdd.NewCurrPos =
new PointDef() { X = pFromX + pHeniX * 2, Y = pFromY + pHeniY * 2 };
WillReturn.Add(WillAdd);
};
if (pFromX == 0 && pFromY == 0) { //Aからジャンプする場合
JumpAct(0, 2);
JumpAct(1, 1);
JumpAct(2, 0);
}
if (pFromX == 2 && pFromY == 0) { //Bからジャンプする場合
JumpAct(-1, 1);
JumpAct(0, 2);
JumpAct(1, 1);
}
if (pFromX == 4 && pFromY == 0) { //Cからジャンプする場合
JumpAct(-1, 1);
JumpAct(0, 2);
}
if (pFromX == 1 && pFromY == 1) { //Dからジャンプする場合
JumpAct(1, 1);
}
if (pFromX == 3 && pFromY == 1) { //Eからジャンプする場合
JumpAct(-1, 1);
}
if (pFromX == 0 && pFromY == 2) { //Fからジャンプする場合
JumpAct(1, -1);
JumpAct(2, 0);
JumpAct(1, 1);
}
if (pFromX == 2 && pFromY == 2) { //Gからジャンプする場合
JumpAct(-1, -1);
JumpAct(1, -1);
JumpAct(-1, 1);
JumpAct(1, 1);
}
if (pFromX == 4 && pFromY == 2) { //Hからジャンプする場合
JumpAct(-1, -1);
JumpAct(-2, 0);
JumpAct(-1, 1);
}
if (pFromX == 1 && pFromY == 3) { //Iからジャンプする場合
JumpAct(1, -1);
}
if (pFromX == 3 && pFromY == 3) { //Jからジャンプする場合
JumpAct(-1, -1);
}
if (pFromX == 0 && pFromY == 4) { //Kからジャンプする場合
JumpAct(0, -2);
JumpAct(1, -1);
JumpAct(2, 0);
}
if (pFromX == 2 && pFromY == 4) { //Lからジャンプする場合
JumpAct(-1, -1);
JumpAct(0, -2);
JumpAct(1, -1);
}
if (pFromX == 4 && pFromY == 4) { //Mからジャンプする場合
JumpAct(0, -2);
JumpAct(-1, -1);
JumpAct(-2, 0);
}
return WillReturn.ToArray();
}
//カエルがジャンプできるかを判定
static bool CanJump(bool[,] pBanArr, int pFromX, int pFromY, int pHeniX, int pHeniY)
{
if (pBanArr[pFromX + pHeniX, pFromY + pHeniY] == false) return false;
if (pBanArr[pFromX + pHeniX * 2, pFromY + pHeniY * 2]) return false;
return true;
}
//盤面を出力
static void PrintBan(bool[,] pBanArr)
{
var sb = new System.Text.StringBuilder();
for (int Y = 0; Y <= UB; Y++) {
for (int X = 0; X <= UB; X++) {
if ((X + Y) % 2 == 0) {
if (pBanArr[X, Y]) sb.Append('カ');
else sb.Append('○');
}
else sb.Append(' ');
}
sb.AppendLine();
}
Console.WriteLine(sb.ToString());
}
}
