using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
const int UB_X = 5;
const int UB_Y = 4;
struct PointDef
{
internal int X;
internal int Y;
}
static char[,] mQuestionArr = new char[UB_X + 1, UB_Y + 1]; //問題の初期盤面
static char mUkiwaChar; //赤い浮き輪の文字
//問題を定義
static void QuestionDef()
{
string[] Q01Arr ={"１２３３４５",
"６２３７８８",
"６６９ＡＡ８",
"□９９ＡＡＢ",
"□ＣＤＤＥＢ"};
string[] Q02Arr ={"１□２３３４",
"５２２□３４",
"６７８９ＡＡ",
"ＢＢＣ９ＡＡ",
"ＢＤＣＣＥＥ"};
string[] Q03Arr ={"１２２３３４",
"５□２６４４",
"５５７７□８",
"９ＡＢＣＣ８",
"ＡＡＤＣＣＥ"};
string[] SampleArr ={"１１２３３４",
"１５６６７７",
"８８６６９９",
"８ＡＢＣＣ９",
"ＤＡＡＥ□□"};
string[] wkP = SampleArr;
for (int X = 0; X <= UB_X; X++) {
for (int Y = 0; Y <= UB_Y; Y++) {
mQuestionArr[X, Y] = wkP[Y][X];
}
}
}
struct JyoutaiDef
{
internal char[,] BanArr;
internal int Level;
internal List<string> Log;
}
static void Main()
{
//問題を定義
QuestionDef();
//ピースの配置情報を取得
DerivePieceHeniListDict();
//赤い浮き輪の文字を設定
SetUkiwaChar();
//ピースの変位情報のDense_Rankを取得
DerivePieceHeniDnDict();
var Stk = new Stack<JyoutaiDef>();
JyoutaiDef WillPush;
WillPush.BanArr = mQuestionArr;
WillPush.Level = 0;
WillPush.Log = new List<string>();
WillPush.Log.Add(BanToStr(WillPush.BanArr));
Stk.Push(WillPush);
var MinTesuuDict = new Dictionary<ulong, int>();
MinTesuuDict.Add(GetHash(WillPush.BanArr), 0);
List<string> AnswerLog = null;
int AnswerLevel = int.MaxValue;
while (Stk.Count > 0) {
JyoutaiDef Popped = Stk.Pop();
if (IsClear(Popped.BanArr)) {
if (AnswerLog == null && Popped.Level == AnswerLevel
|| Popped.Level < AnswerLevel) {
AnswerLog = Popped.Log;
AnswerLevel = Popped.Level;
Console.WriteLine("{0}手の解を発見", Popped.Level);
}
continue;
}
//下限値枝切り
if (Popped.Level + DeriveNeedMinTesuu(Popped.BanArr) >= AnswerLevel) continue;
foreach (char EachPiece in "１２３４５６７８９ＡＢＣＤＥ") {
//盤面とピースを引数として、1手後の盤面のListを返す
List<char[,]> MovedArrList = DeriveMovedArrList(Popped.BanArr, EachPiece);
foreach (char[,] EachMovedArr in MovedArrList) {
WillPush.BanArr = EachMovedArr;
WillPush.Level = Popped.Level + 1;
//メモ化探索
int MinTesuu;
ulong Hash = GetHash(EachMovedArr);
if (MinTesuuDict.TryGetValue(Hash, out MinTesuu)) {
if (MinTesuu <= WillPush.Level) continue;
}
MinTesuuDict[Hash] = WillPush.Level;
WillPush.Log = new List<string>(Popped.Log);
WillPush.Log.Add(BanToStr(WillPush.BanArr));
Stk.Push(WillPush);
}
}
}
for (int I = 0; I <= AnswerLog.Count - 1; I++) {
Console.WriteLine("{0}手目", I);
Console.WriteLine(AnswerLog[I]);
}
}
//ピースの配置情報を取得
static Dictionary<char, List<PointDef>> mPieceHeniListDict = new Dictionary<char, List<PointDef>>();
static void DerivePieceHeniListDict()
{
char[] PieceArr = mQuestionArr.Cast<char>().Where(X => X != '□').Distinct().ToArray();
Array.Sort(PieceArr);
foreach (char EachPiece in PieceArr) {
bool FirstFlag = true;
PointDef GentenPos = new PointDef() { X = -1, Y = -1 };
for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
if (mQuestionArr[LoopX, LoopY] != EachPiece) continue;
if (FirstFlag) {
FirstFlag = false;
GentenPos.X = LoopX;
GentenPos.Y = LoopY;
mPieceHeniListDict.Add(EachPiece, new List<PointDef>());
}
//原点 + 変位ベクトル = カレント座標
//を移項
PointDef HeniVect;
HeniVect.X = LoopX - GentenPos.X;
HeniVect.Y = LoopY - GentenPos.Y;
mPieceHeniListDict[EachPiece].Add(HeniVect);
}
}
}
}
//赤い浮き輪の文字を設定
static void SetUkiwaChar()
{
var wkList = new List<PointDef>();
wkList.Add(new PointDef() { X = 0, Y = 0 });
wkList.Add(new PointDef() { X = 1, Y = 0 });
wkList.Add(new PointDef() { X = 0, Y = 1 });
wkList.Add(new PointDef() { X = 1, Y = 1 });
foreach (var EachPair in mPieceHeniListDict) {
if (EachPair.Value.SequenceEqual(wkList))
mUkiwaChar = EachPair.Key;
}
}
//ピースの変位情報のDense_Rankを取得
static Dictionary<char, ulong> mPieceHeniDnDict = new Dictionary<char, ulong>();
static void DerivePieceHeniDnDict()
{
var wkList = new List<string>();
foreach (var EachPair in mPieceHeniListDict) {
var sb = new System.Text.StringBuilder();
foreach (PointDef EachPoint in EachPair.Value) {
sb.AppendFormat("{0}{1}", EachPoint.X, EachPoint.Y);
}
string wkStr = sb.ToString();
if (wkList.Contains(wkStr) == false)
wkList.Add(wkStr);
mPieceHeniDnDict.Add(EachPair.Key, 1 + (ulong)wkList.IndexOf(wkStr));
}
}
//クリア判定
static bool IsClear(char[,] pBanArr)
{
return pBanArr[UB_X, UB_Y] == mUkiwaChar;
}
//最小の残り手数を返す(下限値枝切り用)
static int DeriveNeedMinTesuu(char[,] pBanArr)
{
PointDef wkPos = DerivePiecePos(pBanArr, mUkiwaChar);
int X = wkPos.X;
int Y = wkPos.Y;
if (X == 0 && Y == 0) return 25;
if (X == 1 && Y == 0) return 21;
if (X == 2 && Y == 0) return 17;
if (X == 3 && Y == 0) return 13;
if (X == 4 && Y == 0) return 9;
if (X == 0 && Y == 1) return 21;
if (X == 1 && Y == 1) return 17;
if (X == 2 && Y == 1) return 13;
if (X == 3 && Y == 1) return 9;
if (X == 4 && Y == 1) return 5;
if (X == 0 && Y == 2) return 17;
if (X == 1 && Y == 2) return 13;
if (X == 2 && Y == 2) return 9;
if (X == 3 && Y == 2) return 5;
if (X == 4 && Y == 2) return 1;
if (X == 0 && Y == 3) return 13;
if (X == 1 && Y == 3) return 9;
if (X == 2 && Y == 3) return 5;
if (X == 3 && Y == 3) return 1;
if (X == 4 && Y == 3) return 0;
return 0;
}
struct MoveInfoDef
{
internal char[,] BanArr;
internal PointDef FromPos;
}
//盤面とピースを引数として、1手後の盤面のListを返す
static List<char[,]> DeriveMovedArrList(char[,] pBanArr, char pPiece)
{
var WillReturn = new List<char[,]>();
PointDef PiecePos = DerivePiecePos(pBanArr, pPiece);
var Stk = new Stack<MoveInfoDef>();
MoveInfoDef WillPush;
WillPush.BanArr = pBanArr;
WillPush.FromPos = PiecePos;
Stk.Push(WillPush);
var VisitedSet = new HashSet<ulong>();
while (Stk.Count > 0) {
MoveInfoDef Popped = Stk.Pop();
MoveInfoDef[] MovedInfoArr = DeriveMovedInfoArr(Popped.BanArr, pPiece, Popped.FromPos);
foreach (MoveInfoDef EachJyoutai in MovedInfoArr) {
ulong CurrHash = GetHash(EachJyoutai.BanArr);
if (CurrHash == GetHash(pBanArr)) continue;
if (VisitedSet.Add(CurrHash) == false) continue;
WillReturn.Add(EachJyoutai.BanArr);
//1手で複数マス動けるピースの場合
if (mPieceHeniListDict[pPiece].Count <= 2)
Stk.Push(EachJyoutai);
}
}
return WillReturn;
}
//盤面とピースを引数として、移動情報の配列を返す
static MoveInfoDef[] DeriveMovedInfoArr(char[,] pBanArr, char pPiece, PointDef pFromPos)
{
var WillReturn = new List<MoveInfoDef>();
//変位ベクトルのList
var HeniList = new List<PointDef>();
HeniList.Add(new PointDef() { X = 0, Y = -1 });
HeniList.Add(new PointDef() { X = 0, Y = +1 });
HeniList.Add(new PointDef() { X = -1, Y = 0 });
HeniList.Add(new PointDef() { X = +1, Y = 0 });
foreach (PointDef EachHeni in HeniList) {
bool CanMove = true;
foreach (PointDef EachPos in mPieceHeniListDict[pPiece]) {
int X = pFromPos.X + EachPos.X + EachHeni.X;
int Y = pFromPos.Y + EachPos.Y + EachHeni.Y;
if (X < 0 || UB_X < X) CanMove = false;
if (Y < 0 || UB_Y < Y) CanMove = false;
if (CanMove == false) break;
if (pBanArr[X, Y] != '□' && pBanArr[X, Y] != pPiece)
CanMove = false;
}
if (CanMove == false) continue;
//移動可能な場合
char[,] wkArr = (char[,])pBanArr.Clone();
foreach (PointDef EachPos in mPieceHeniListDict[pPiece]) {
int X = pFromPos.X + EachPos.X;
int Y = pFromPos.Y + EachPos.Y;
wkArr[X, Y] = '□'; //空白で埋める
}
foreach (PointDef EachPos in mPieceHeniListDict[pPiece]) {
int X = pFromPos.X + EachPos.X + EachHeni.X;
int Y = pFromPos.Y + EachPos.Y + EachHeni.Y;
wkArr[X, Y] = pPiece; //ピースで埋める
}
MoveInfoDef WillAdd;
WillAdd.BanArr = wkArr;
WillAdd.FromPos = new PointDef() { X = pFromPos.X + EachHeni.X, Y = pFromPos.Y + EachHeni.Y };
WillReturn.Add(WillAdd);
}
return WillReturn.ToArray();
}
//盤面とピースを引数として、ピースの左上の座標を返す
static PointDef DerivePiecePos(char[,] pBanArr, char pPiece)
{
for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
if (pBanArr[LoopX, LoopY] == pPiece) {
return new PointDef() { X = LoopX, Y = LoopY };
}
}
}
return new PointDef() { X = -1, Y = -1 };
}
//ハッシュ値を求める
static ulong GetHash(char[,] pBanArr)
{
var NumList = new List<ulong>();
var AppearedSet = new HashSet<char>();
for (int X = 0; X <= UB_X; X++) {
for (int Y = 0; Y <= UB_Y; Y++) {
char CurrChar = pBanArr[X, Y];
if (CurrChar == '□') {
NumList.Add(0);
}
else if (AppearedSet.Add(CurrChar)) {
NumList.Add(mPieceHeniDnDict[CurrChar]);
}
}
}
//9の17乗=16677181699666600なので9進数ならオーバーフローしない
ulong WillReturn = 0;
foreach (ulong EachULong in NumList) {
WillReturn *= 9;
WillReturn += EachULong;
}
return WillReturn;
}
//盤面を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();
}
}
