using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
const int UB_X = 2;
const int UB_Y = 3;
struct PointDef
{
internal int X;
internal int Y;
}
static char[,] mGoalArr = new char[UB_X + 1, UB_Y + 1]; //ゴールの盤面
//問題を定義
static void QuestionDef()
{
string[] Q05Arr ={"Ｓ□黄",
"赤赤黄",
"１２３",
"青緑青"};
string[] Q06Arr ={"Ｓ□赤",
"青緑黄",
"１２３",
"赤黄青"};
string[] Q07Arr ={"赤□Ｓ",
"黄赤青",
"１２３",
"緑青黄"};
string[] wkP = Q05Arr;
for (int X = 0; X <= UB_X; X++) {
for (int Y = 0; Y <= UB_Y; Y++) {
mGoalArr[X, Y] = wkP[Y][X];
}
}
}
static void Main()
{
//問題を定義
QuestionDef();
//双方向に半分全探索で解く
for (int Depth = 2; Depth < int.MaxValue; Depth++) {
int SeiDepth = Depth / 2;
int RevDepth = Depth / 2;
if (Depth % 2 == 1) SeiDepth++;
IEnumerable<JyoutaiDef> SeiArr = ExecDFS(SeiDepth, true);
JyoutaiDef[] RevArr = ExecDFS(RevDepth, false).ToArray();
var HashDict = new Dictionary<long, int>();
for (int I = 0; I <= RevArr.GetUpperBound(0); I++) {
HashDict.Add(GetHash(RevArr[I].BanArr), I);
}
foreach (JyoutaiDef EachSei in SeiArr) {
long wkHash = GetHash(EachSei.BanArr);
if (HashDict.ContainsKey(wkHash)) {
Console.WriteLine("解を発見");
for (int I = 0; I <= EachSei.Log.Count - 1; I++) {
Console.WriteLine("{0}手目", I);
Console.WriteLine(EachSei.Log[I]);
}
int wkInd = HashDict[wkHash];
int CurrLevel = EachSei.Log.Count;
for (int I = RevArr[wkInd].Log.Count - 2; 0 <= I; I--) {
Console.WriteLine("{0}手目", CurrLevel++);
Console.WriteLine(RevArr[wkInd].Log[I]);
}
return;
}
}
}
}
struct JyoutaiDef
{
internal char[,] BanArr;
internal int Level;
internal List<string> Log;
}
static string[] mInitStr ={"緑□Ｓ",
"黄赤黄",
"１２３",
"青赤青"};
//双方向に半分全探索
static IEnumerable<JyoutaiDef> ExecDFS(int pLevelLimit, bool pIsSei)
{
var Stk = new Stack<JyoutaiDef>();
JyoutaiDef WillPush;
if (pIsSei) {
WillPush.BanArr = new char[UB_X + 1, UB_Y + 1];
for (int X = 0; X <= UB_X; X++) {
for (int Y = 0; Y <= UB_Y; Y++) {
WillPush.BanArr[X, Y] = mInitStr[Y][X];
}
}
}
else WillPush.BanArr = mGoalArr;
WillPush.Level = 0;
WillPush.Log = new List<string>();
WillPush.Log.Add(BanToStr(WillPush.BanArr));
Stk.Push(WillPush);
var MinTesuuDict = new Dictionary<long, int>();
MinTesuuDict.Add(GetHash(WillPush.BanArr), 0);
while (Stk.Count > 0) {
JyoutaiDef Popped = Stk.Pop();
//クリア判定
if (Popped.Level == pLevelLimit) {
yield return Popped;
continue;
}
//空白マスの座標を求める
int SpaceX, SpaceY;
DeriveSpaceMasu(Popped.BanArr, out SpaceX, out SpaceY);
//空白マスの4近傍の座標のListを求める
PointDef[] KinbouArr = DeriveKinbouArr(SpaceX, SpaceY);
//Push処理を行う
foreach (PointDef EachKinbou in KinbouArr) {
WillPush.BanArr = (char[,])Popped.BanArr.Clone();
WillPush.BanArr[SpaceX, SpaceY] = Popped.BanArr[EachKinbou.X, EachKinbou.Y];
WillPush.BanArr[EachKinbou.X, EachKinbou.Y] = '□';
WillPush.Level = Popped.Level + 1;
WillPush.Log = new List<string>(Popped.Log);
WillPush.Log.Add(BanToStr(WillPush.BanArr));
int MinTesuu;
long wkHash = GetHash(WillPush.BanArr);
if (MinTesuuDict.TryGetValue(wkHash, out MinTesuu)) {
if (MinTesuu <= WillPush.Level) continue;
}
MinTesuuDict[wkHash] = WillPush.Level;
Stk.Push(WillPush);
}
}
}
//空白マスの座標を求める
static void DeriveSpaceMasu(char[,] pBanArr, out int pX, out int pY)
{
pX = pY = -1;
for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
if (pBanArr[LoopX, LoopY] == '□') {
pX = LoopX; pY = LoopY;
return;
}
}
}
}
//4近傍の座標の配列を求める
static PointDef[] DeriveKinbouArr(int pBaseX, int pBaseY)
{
var WillReturn = new List<PointDef>();
Action<int, int> wkAct = (pX, pY) =>
{
if (pX < 0 || UB_X < pX) return;
if (pY < 0 || UB_Y < pY) return;
WillReturn.Add(new PointDef() { X = pX, Y = pY });
};
wkAct(pBaseX, pBaseY - 1);
wkAct(pBaseX, pBaseY + 1);
wkAct(pBaseX - 1, pBaseY);
wkAct(pBaseX + 1, pBaseY);
return WillReturn.ToArray();
}
//ハッシュ値を求める
static long GetHash(char[,] pBanArr)
{
var sb = new System.Text.StringBuilder();
for (int X = 0; X <= UB_X; X++) {
for (int Y = 0; Y <= UB_Y; Y++) {
char CurrChar = pBanArr[X, Y];
if (CurrChar == '緑') sb.Append("0");
if (CurrChar == '□') sb.Append("1");
if (CurrChar == 'Ｓ') sb.Append("2");
if (CurrChar == '黄') sb.Append("3");
if (CurrChar == '赤') sb.Append("4");
if (CurrChar == '１') sb.Append("5");
if (CurrChar == '２') sb.Append("6");
if (CurrChar == '３') sb.Append("7");
if (CurrChar == '青') sb.Append("8");
}
}
return long.Parse(sb.ToString());
}
//盤面をString型で表現
static string BanToStr(char[,] 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();
}
}
