using System;
using System.Collections.Generic;
class Program
{
const int UB_X = 5;
const int UB_Y = 4;
struct PointDef
{
internal int X;
internal int Y;
}
struct JyoutaiDef
{
internal char[,] BanArr;
internal int Level;
internal List<string> Log;
}
static void Main()
{
var sw = System.Diagnostics.Stopwatch.StartNew();
string[] InitArr ={"ＥＤ９９□□",
"ＥＤ８８３２",
"ＣＣ７６３２",
"ＢＢ５５１１",
"ＡＡ４４１１"};
var Stk = new Stack<JyoutaiDef>();
JyoutaiDef WillPush;
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] = InitArr[Y][X];
}
}
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 = 44;
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);
}
}
}
if (AnswerLog == null) Console.WriteLine("解はありません");
else {
for (int I = 0; I <= AnswerLog.Count - 1; I++) {
Console.WriteLine("{0}手目", I);
Console.WriteLine(AnswerLog[I]);
}
}
Console.WriteLine("経過時間={0}", sw.Elapsed);
}
//クリア判定
static bool IsClear(char[,] pBanArr)
{
return pBanArr[0, 0] == '１';
}
//最小の残り手数を返す(下限値枝切り用)
static int DeriveNeedMinTesuu(char[,] pBanArr)
{
PointDef wkPos = DerivePiecePos(pBanArr, '１');
int X = wkPos.X;
int Y = wkPos.Y;
if (X == 1 && Y == 0) return 1;
if (X == 2 && Y == 0) return 5;
if (X == 3 && Y == 0) return 9;
if (X == 4 && Y == 0) return 13;
if (X == 0 && Y == 1) return 1;
if (X == 1 && Y == 1) return 5;
if (X == 2 && Y == 1) return 9;
if (X == 3 && Y == 1) return 13;
if (X == 4 && Y == 1) return 17;
if (X == 0 && Y == 2) return 1;
if (X == 1 && Y == 2) return 9;
if (X == 2 && Y == 2) return 13;
if (X == 3 && Y == 2) return 17;
if (X == 4 && Y == 2) return 21;
if (X == 0 && Y == 3) return 9;
if (X == 1 && Y == 3) return 13;
if (X == 2 && Y == 3) return 17;
if (X == 3 && Y == 3) return 21;
if (X == 4 && Y == 3) return 25;
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 (pPiece != '１') Stk.Push(EachJyoutai);
}
}
return WillReturn;
}
//盤面とピースを引数として、移動情報の配列を返す
static MoveInfoDef[] DeriveMovedInfoArr(char[,] pBanArr, char pPiece, PointDef pFromPos)
{
var WillReturn = new List<MoveInfoDef>();
int FromX = pFromPos.X, FromY = pFromPos.Y;
Action<char[,], int, int> AddAct1 = (pArr, pToX, pToY) =>
{
MoveInfoDef WillAdd;
WillAdd.BanArr = pArr;
WillAdd.FromPos = new PointDef() { X = pToX, Y = pToY };
WillReturn.Add(WillAdd);
};
if (pPiece == '１') {
//上に移動
if (IsSpace(pBanArr, FromX, FromY - 1)
&& IsSpace(pBanArr, FromX + 1, FromY - 1)) {
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[FromX, FromY - 1] = wkArr[FromX + 1, FromY - 1] = '１';
wkArr[FromX, FromY] = wkArr[FromX + 1, FromY] = '１';
wkArr[FromX, FromY + 1] = wkArr[FromX + 1, FromY + 1] = '□';
AddAct1(wkArr, FromX, FromY - 1);
}
//下に移動
if (IsSpace(pBanArr, FromX, FromY + 2)
&& IsSpace(pBanArr, FromX + 1, FromY + 2)) {
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[FromX, FromY] = wkArr[FromX + 1, FromY] = '□';
wkArr[FromX, FromY + 1] = wkArr[FromX + 1, FromY + 1] = '１';
wkArr[FromX, FromY + 2] = wkArr[FromX + 1, FromY + 2] = '１';
AddAct1(wkArr, FromX, FromY + 1);
}
//左に移動
if (IsSpace(pBanArr, FromX - 1, FromY)
&& IsSpace(pBanArr, FromX - 1, FromY + 1)) {
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[FromX - 1, FromY] = '１';
wkArr[FromX - 1, FromY + 1] = '１';
wkArr[FromX, FromY] = '１';
wkArr[FromX, FromY + 1] = '１';
wkArr[FromX + 1, FromY] = wkArr[FromX + 1, FromY + 1] = '□';
AddAct1(wkArr, FromX - 1, FromY);
}
//右に移動
if (IsSpace(pBanArr, FromX + 2, FromY)
&& IsSpace(pBanArr, FromX + 2, FromY + 1)) {
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[FromX + 2, FromY] = '１';
wkArr[FromX + 2, FromY + 1] = '１';
wkArr[FromX + 1, FromY] = '１';
wkArr[FromX + 1, FromY + 1] = '１';
wkArr[FromX, FromY] = wkArr[FromX, FromY + 1] = '□';
AddAct1(wkArr, FromX + 1, FromY);
}
}
if (pPiece == '２' || pPiece == '３' || pPiece == 'Ｄ' || pPiece == 'Ｅ') {
//上に移動
if (IsSpace(pBanArr, FromX, FromY - 1)) {
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[FromX, FromY - 1] = pPiece;
wkArr[FromX, FromY] = pPiece;
wkArr[FromX, FromY + 1] = '□';
AddAct1(wkArr, FromX, FromY - 1);
}
//下に移動
if (IsSpace(pBanArr, FromX, FromY + 2)) {
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[FromX, FromY] = '□';
wkArr[FromX, FromY + 1] = pPiece;
wkArr[FromX, FromY + 2] = pPiece;
AddAct1(wkArr, FromX, FromY + 1);
}
//左に移動
if (IsSpace(pBanArr, FromX - 1, FromY)
&& IsSpace(pBanArr, FromX - 1, FromY + 1)) {
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[FromX - 1, FromY] = pPiece;
wkArr[FromX - 1, FromY + 1] = pPiece;
wkArr[FromX, FromY] = wkArr[FromX, FromY + 1] = '□';
AddAct1(wkArr, FromX - 1, FromY);
}
//右に移動
if (IsSpace(pBanArr, FromX + 1, FromY)
&& IsSpace(pBanArr, FromX + 1, FromY + 1)) {
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[FromX + 1, FromY] = pPiece;
wkArr[FromX + 1, FromY + 1] = pPiece;
wkArr[FromX, FromY] = wkArr[FromX, FromY + 1] = '□';
AddAct1(wkArr, FromX + 1, FromY);
}
}
if (pPiece == '４' || pPiece == '５' || pPiece == '８' || pPiece == '９'
|| pPiece == 'Ａ' || pPiece == 'Ｂ' || pPiece == 'Ｃ') {
//上に移動
if (IsSpace(pBanArr, FromX, FromY - 1)
&& IsSpace(pBanArr, FromX + 1, FromY - 1)) {
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[FromX, FromY - 1] = pPiece;
wkArr[FromX + 1, FromY - 1] = pPiece;
wkArr[FromX, FromY] = wkArr[FromX + 1, FromY] = '□';
AddAct1(wkArr, FromX, FromY - 1);
}
//下に移動
if (IsSpace(pBanArr, FromX, FromY + 1)
&& IsSpace(pBanArr, FromX + 1, FromY + 1)) {
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[FromX, FromY] = wkArr[FromX + 1, FromY] = '□';
wkArr[FromX, FromY + 1] = pPiece;
wkArr[FromX + 1, FromY + 1] = pPiece;
AddAct1(wkArr, FromX, FromY + 1);
}
//左に移動
if (IsSpace(pBanArr, FromX - 1, FromY)) {
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[FromX - 1, FromY] = pPiece;
wkArr[FromX, FromY] = pPiece;
wkArr[FromX + 1, FromY] = '□';
AddAct1(wkArr, FromX - 1, FromY);
}
//右に移動
if (IsSpace(pBanArr, FromX + 2, FromY)) {
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[FromX, FromY] = '□';
wkArr[FromX + 1, FromY] = pPiece;
wkArr[FromX + 2, FromY] = pPiece;
AddAct1(wkArr, FromX + 1, FromY);
}
}
if (pPiece == '６' || pPiece == '７') {
Action<int, int> AddAct2 = (pToX, pToY) =>
{
if (IsSpace(pBanArr, pToX, pToY) == false) return;
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[pToX, pToY] = pPiece; wkArr[FromX, FromY] = '□';
MoveInfoDef WillAdd;
WillAdd.BanArr = wkArr;
WillAdd.FromPos = new PointDef() { X = pToX, Y = pToY };
WillReturn.Add(WillAdd);
};
//上に移動
AddAct2(FromX, FromY - 1);
//下に移動
AddAct2(FromX, FromY + 1);
//左に移動
AddAct2(FromX - 1, FromY);
//右に移動
AddAct2(FromX + 1, FromY);
}
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 bool IsSpace(char[,] pBanArr, int pX, int pY)
{
if (pX < 0 || UB_X < pX) return false;
if (pY < 0 || UB_Y < pY) return false;
return pBanArr[pX, pY] == '□';
}
//ハッシュ値を求める
static ulong GetHash(char[,] pBanArr)
{
var sb = new System.Text.StringBuilder();
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 == '１') {
if (AppearedSet.Add(CurrChar)) sb.Append(4);
}
else if (CurrChar == '４' || CurrChar == '５' || CurrChar == '８'
|| CurrChar == '９' || CurrChar == 'Ａ' || CurrChar == 'Ｂ'
|| CurrChar == 'Ｃ') {
if (AppearedSet.Add(CurrChar)) sb.Append(3);
}
else if (CurrChar == '２' || CurrChar == '３' || CurrChar == 'Ｄ'
|| CurrChar == 'Ｅ') {
if (AppearedSet.Add(CurrChar)) sb.Append(2);
}
else if (CurrChar == '６' || CurrChar == '７') {
if (AppearedSet.Add(CurrChar)) sb.Append(1);
}
else sb.Append(0);
}
}
//8の15乗=35184372088832なので8進数ならオーバーフローしない
return Convert.ToUInt64(sb.ToString(), 8);
}
//盤面を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();
}
}
各ピースをスライドさせ、家康が左上の天下統一に到着すればクリアです。