using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
const int UB = 6 - 1;
struct JyoutaiDef
{
internal char[,] BanArr;
internal int Level;
internal List<string> Log;
}
static void Main()
{
var Que = new Queue<JyoutaiDef>();
JyoutaiDef WillEnqueue;
WillEnqueue.BanArr = new char[UB + 1, UB + 1];
string[] wkStrArr ={"JAA B ",
"JCD BK",
"JCDXXK",
"LLLE K",
" FEGG",
"HHFII "};
for (int Y = 0; Y <= wkStrArr.GetUpperBound(0); Y++) {
for (int X = 0; X <= wkStrArr[Y].Length - 1; X++) {
WillEnqueue.BanArr[X, Y] = wkStrArr[Y][X];
}
}
//車のIDの配列
char[] CarIDArr =
WillEnqueue.BanArr.Cast<char>().Where(A => A != ' ').Distinct().ToArray();
Array.Sort<char>(CarIDArr);
WillEnqueue.Level = 0;
WillEnqueue.Log = new List<string>();
WillEnqueue.Log.Add(BanToStr(WillEnqueue.BanArr));
Que.Enqueue(WillEnqueue);
var VisitedSet = new HashSet<string>();
VisitedSet.Add(GetHash(WillEnqueue.BanArr));
while (Que.Count > 0) {
JyoutaiDef Dequeued = Que.Dequeue();
//クリア判定
if (Dequeued.BanArr[4, 2] == 'X' && Dequeued.BanArr[5, 2] == 'X') {
Console.WriteLine("{0}手の解を発見", Dequeued.Level);
for (int I = 0; I <= Dequeued.Log.Count - 1; I++) {
Console.WriteLine("{0}手目", I);
Console.WriteLine(Dequeued.Log[I]);
}
return;
}
foreach (char EachCarID in CarIDArr) {
MoveInfoDef wkMoveInfo = DeriveMoveInfo(EachCarID, Dequeued.BanArr);
foreach (PointDef EachHeni in wkMoveInfo.HeniArr) {
WillEnqueue.BanArr = (char[,])Dequeued.BanArr.Clone();
//移動後の両端の座標を求める
int MovedFromX = wkMoveInfo.FromPos.X + EachHeni.X;
int MovedFromY = wkMoveInfo.FromPos.Y + EachHeni.Y;
int MovedToX = wkMoveInfo.ToPos.X + EachHeni.X;
int MovedToY = wkMoveInfo.ToPos.Y + EachHeni.Y;
//空白に変更するループ
int StaX = Math.Min(MovedFromX, wkMoveInfo.FromPos.X);
int StaY = Math.Min(MovedFromY, wkMoveInfo.FromPos.Y);
int EndX = Math.Max(MovedToX, wkMoveInfo.ToPos.X);
int EndY = Math.Max(MovedToY, wkMoveInfo.ToPos.Y);
for (int X = StaX; X <= EndX; X++) {
for (int Y = StaY; Y <= EndY; Y++) {
WillEnqueue.BanArr[X, Y] = ' ';
}
}
//車IDに変更するループ
for (int X = MovedFromX; X <= MovedToX; X++) {
for (int Y = MovedFromY; Y <= MovedToY; Y++) {
WillEnqueue.BanArr[X, Y] = EachCarID;
}
}
//訪問済ノードなら枝切り
if (VisitedSet.Add(GetHash(WillEnqueue.BanArr)) == false)
continue;
WillEnqueue.Level = Dequeued.Level + 1;
WillEnqueue.Log = new List<string>(Dequeued.Log);
WillEnqueue.Log.Add(BanToStr(WillEnqueue.BanArr));
Que.Enqueue(WillEnqueue);
}
}
}
}
struct PointDef
{
internal int X;
internal int Y;
}
//車の移動情報
struct MoveInfoDef
{
internal PointDef FromPos; //両端の開始座標
internal PointDef ToPos; //両端の終了座標
internal PointDef[] HeniArr; //移動変位の配列
}
//車のIDを引数として、車の移動情報を返す
static MoveInfoDef DeriveMoveInfo(char pCarID, char[,] pBanArr)
{
MoveInfoDef MoveInfo = new MoveInfoDef();
bool CanMoveYoko = DeriveCanMoveYoko(pCarID);
bool WillBreak = false;
for (int LoopX = 0; LoopX <= UB; LoopX++) {
for (int LoopY = 0; LoopY <= UB; LoopY++) {
if (pBanArr[LoopX, LoopY] != pCarID) continue;
MoveInfo.FromPos = new PointDef() { X = LoopX, Y = LoopY };
int CarLength = DeriveCarLength(pCarID);
if (CanMoveYoko)
MoveInfo.ToPos = new PointDef() { X = LoopX + CarLength - 1, Y = LoopY };
else MoveInfo.ToPos = new PointDef() { X = LoopX, Y = LoopY + CarLength - 1 };
WillBreak = true;
break;
}
if (WillBreak) break;
}
var HeniList = new List<PointDef>();
Func<int, int, bool> AddFunc = (pI, pBasePos) =>
{
if (pBasePos + pI > UB) return false;
if (pBasePos + pI < 0) return false;
if (CanMoveYoko) {
if (pBanArr[pBasePos + pI, MoveInfo.FromPos.Y] != ' ') return false;
HeniList.Add(new PointDef() { X = pI, Y = 0 });
}
else {
if (pBanArr[MoveInfo.FromPos.X, pBasePos + pI] != ' ') return false;
HeniList.Add(new PointDef() { X = 0, Y = pI });
}
return true;
};
//変位が正の場合
for (int I = 1; I <= UB; I++) {
if (AddFunc(I, CanMoveYoko ? MoveInfo.ToPos.X : MoveInfo.ToPos.Y) == false)
break;
}
//変位が負の場合
for (int I = -1; I >= -UB; I--) {
if (AddFunc(I, CanMoveYoko ? MoveInfo.FromPos.X : MoveInfo.FromPos.Y) == false)
break;
}
MoveInfo.HeniArr = HeniList.ToArray();
return MoveInfo;
}
//車が横に移動可かを返す
static bool DeriveCanMoveYoko(char pCarID)
{
return "AGHILX".Contains(pCarID);
}
//車の長さを返す
static int DeriveCarLength(char pCarID)
{
if ('A' <= pCarID && pCarID <= 'I') return 2;
if ('J' <= pCarID && pCarID <= 'L') return 3;
if (pCarID == 'X') return 2;
return -1;
}
//盤面をハッシュ値に変換
static string GetHash(char[,] pBanArr)
{
var sb = new System.Text.StringBuilder();
var AppearedCharSet = new HashSet<char>();
for (int X = 0; X <= UB; X++) {
for (int Y = 0; Y <= UB; Y++) {
char wkChar = pBanArr[X, Y];
if (wkChar == ' ') continue;
if (AppearedCharSet.Add(wkChar)) {
sb.AppendFormat("{0}{1}{2}", wkChar, X, Y);
}
}
}
return sb.ToString();
}
//盤面をString型に変換
static string BanToStr(char[,] pBanArr)
{
//全角に変換
Func<char, char> ConvZenkakuFunc = pChar =>
{
if (pChar == ' ') return ' ';
return (char)('Ａ' + pChar - 'A');
};
var sb = new System.Text.StringBuilder();
for (int Y = 0; Y <= UB; Y++) {
for (int X = 0; X <= UB; X++) {
sb.Append(ConvZenkakuFunc(pBanArr[X, Y]));
}
sb.AppendLine();
}
return sb.ToString();
}
}