using System;
using System.Collections.Generic;
class Program
{
const int UB_X = 6 - 1;
const int UB_Y = 4 - 1;
static void Main()
{
var sw = System.Diagnostics.Stopwatch.StartNew();
//反復深化深さ優先探索で解く
for (int I = 9; I < int.MaxValue; I++) {
Console.WriteLine("レベル制限={0}で深さ優先探索中。経過時間={1}", I, sw.Elapsed);
if (ExecDFS(I)) break;
}
Console.WriteLine("経過時間={0}", sw.Elapsed);
}
struct JyoutaiDef
{
internal bool[,] BanArr;
internal int Level;
internal List<string> Log;
}
//深さ制限を引数として、深さ優先探索
static bool ExecDFS(int pLimitLevel)
{
var Stk = new Stack<JyoutaiDef>();
JyoutaiDef WillPush;
WillPush.BanArr = new bool[UB_X + 1, UB_Y + 1];
for (int X = 0; X <= 2; X++) {
for (int Y = 0; Y <= 2; Y++) {
WillPush.BanArr[X, Y] = true;
}
}
WillPush.Level = 0;
WillPush.Log = new List<string>();
WillPush.Log.Add(BanToStr(WillPush.BanArr));
Stk.Push(WillPush);
var MinTesuuDict = new Dictionary<uint, int>();
MinTesuuDict.Add(GetHash(WillPush.BanArr), 0);
while (Stk.Count > 0) {
JyoutaiDef Popped = Stk.Pop();
//クリア判定
if (IsClear(Popped.BanArr)) {
Console.WriteLine("{0}手の解を発見", pLimitLevel);
for (int I = 0; I <= Popped.Log.Count - 1; I++) {
Console.WriteLine("{0}手目", I);
Console.WriteLine(Popped.Log[I]);
}
return true;
}
//下限値枝切り
if (Popped.Level + DeriveNeedMinTesuu(Popped.BanArr) > pLimitLevel) continue;
for (int X = 0; X <= UB_X; X++) {
for (int Y = 0; Y <= UB_Y; Y++) {
if (Popped.BanArr[X, Y] == false) continue;
//開始座標を引数として、移動可能な座標のListを返す
List<Point> MovePosList = DeriveMovePosList(X, Y, Popped.BanArr);
foreach (Point EachMovePos in MovePosList) {
WillPush.BanArr = (bool[,])(Popped.BanArr).Clone();
WillPush.BanArr[EachMovePos.X, EachMovePos.Y] = true;
WillPush.BanArr[X, Y] = false;
WillPush.Level = Popped.Level + 1;
//メモ化探索
uint wkHash = GetHash(WillPush.BanArr);
int MinTesuu;
if (MinTesuuDict.TryGetValue(wkHash, out MinTesuu)) {
if (MinTesuu <= WillPush.Level) continue;
}
MinTesuuDict[wkHash] = WillPush.Level;
WillPush.Log = new List<string>(Popped.Log);
WillPush.Log.Add(BanToStr(WillPush.BanArr));
Stk.Push(WillPush);
}
}
}
}
return false;
}
//クリア判定
static bool IsClear(bool[,] pBanArr)
{
for (int X = 3; X <= 5; X++) {
for (int Y = 0; Y <= 2; Y++) {
if (pBanArr[X, Y] == false) return false;
}
}
return true;
}
//最小の残り手数を返す(下限値枝切り用)
static int DeriveNeedMinTesuu(bool[,] pBanArr)
{
int WillReturn = 0;
if (pBanArr[5, 0] == false) {
WillReturn += 2;
}
if (pBanArr[5, 1] == false) {
if (pBanArr[4, 2] && pBanArr[3, 3]) WillReturn++;
else if (pBanArr[5, 2] && pBanArr[5, 3]) WillReturn++;
else WillReturn += 2;
}
if (pBanArr[5, 2] == false) {
if (pBanArr[4, 3]) WillReturn++;
else if (pBanArr[5, 3]) WillReturn++;
else WillReturn += 2;
}
if (pBanArr[4, 0] == false) {
if (pBanArr[3, 0] && pBanArr[2, 0]) WillReturn++;
else if (pBanArr[3, 1] && pBanArr[2, 2]) WillReturn++;
else WillReturn += 2;
}
if (pBanArr[4, 1] == false) {
if (pBanArr[3, 1] && pBanArr[2, 1]) WillReturn++;
else if (pBanArr[3, 2] && pBanArr[2, 3]) WillReturn++;
else if (pBanArr[4, 2] && pBanArr[4, 3]) WillReturn++;
else WillReturn += 2;
}
if (pBanArr[4, 2] == false) {
if (pBanArr[3, 1] && pBanArr[2, 0]) WillReturn++;
else if (pBanArr[3, 2] && pBanArr[2, 2]) WillReturn++;
else if (pBanArr[3, 3]) WillReturn++;
else if (pBanArr[4, 3]) WillReturn++;
else if (pBanArr[5, 3]) WillReturn++;
else WillReturn += 2;
}
if (pBanArr[3, 0] == false) {
if (pBanArr[2, 0]) WillReturn++;
else if (pBanArr[2, 1]) WillReturn++;
else WillReturn += 2;
}
if (pBanArr[3, 1] == false) {
if (pBanArr[2, 0]) WillReturn++;
else if (pBanArr[2, 1]) WillReturn++;
else if (pBanArr[2, 2]) WillReturn++;
else WillReturn += 2;
}
if (pBanArr[3, 2] == false) {
if (pBanArr[2, 1]) WillReturn++;
else if (pBanArr[2, 2]) WillReturn++;
else if (pBanArr[2, 3]) WillReturn++;
else if (pBanArr[3, 3]) WillReturn++;
else if (pBanArr[4, 3]) WillReturn++;
else WillReturn += 2;
}
return WillReturn;
}
struct Point
{
internal int X;
internal int Y;
}
//開始座標を引数として、移動可能な座標のListを返す
static List<Point> DeriveMovePosList(int pFromX, int pFromY, bool[,] pBanArr)
{
var WillReturn = new List<Point>();
Action<int, int, bool> wkAct = (pToX, pToY, pIsJump) =>
{
if (pToX < 0 || UB_X < pToX) return;
if (pToY < 0 || UB_Y < pToY) return;
//中点がコインの必要あり
if (pIsJump) {
if (pBanArr[(pFromX + pToX) / 2, (pFromY + pToY) / 2] == false)
return;
}
if (pBanArr[pToX, pToY] == false)
WillReturn.Add(new Point() { X = pToX, Y = pToY });
};
wkAct(pFromX - 2, pFromY - 2, true);
wkAct(pFromX + 0, pFromY - 2, true);
wkAct(pFromX + 2, pFromY - 2, true);
wkAct(pFromX - 1, pFromY - 1, false);
wkAct(pFromX + 0, pFromY - 1, false);
wkAct(pFromX + 1, pFromY - 1, false);
wkAct(pFromX - 2, pFromY, true);
wkAct(pFromX - 1, pFromY, false);
wkAct(pFromX + 1, pFromY, false);
wkAct(pFromX + 2, pFromY, true);
wkAct(pFromX - 1, pFromY + 1, false);
wkAct(pFromX + 0, pFromY + 1, false);
wkAct(pFromX + 1, pFromY + 1, false);
wkAct(pFromX - 2, pFromY + 2, true);
wkAct(pFromX + 0, pFromY + 2, true);
wkAct(pFromX + 2, pFromY + 2, true);
return WillReturn;
}
//盤面をハッシュ値に変換
static uint GetHash(bool[,] pBanArr)
{
var sb = new System.Text.StringBuilder();
for (int X = 0; X <= UB_X; X++) {
for (int Y = 0; Y <= UB_Y; Y++) {
sb.Append(pBanArr[X, Y] ? 1 : 0);
}
}
return Convert.ToUInt32(sb.ToString(), 2);
}
//盤面をString型で表現
static string BanToStr(bool[,] pBanArr)
{
var sb = new System.Text.StringBuilder();
for (int Y = 0; Y <= UB_Y; Y++) {
for (int X = 0; X <= UB_X; X++) {
sb.Append(pBanArr[X, Y] ? '●' : '□');
}
sb.AppendLine();
}
return sb.ToString();
}
}