using System;
using System.Collections.Generic;
class Program
{
const int LevelLimit = 81;
const int UB_X = 3;
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 Que = new Queue<JyoutaiDef>();
JyoutaiDef WillEnqueue;
WillEnqueue.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++) {
WillEnqueue.BanArr[X, Y] = InitArr[Y][X];
}
}
WillEnqueue.Level = 0;
WillEnqueue.Log = new List<string>();
WillEnqueue.Log.Add(BanToStr(WillEnqueue.BanArr));
Que.Enqueue(WillEnqueue);
var VisitedSet = new HashSet<ulong>();
VisitedSet.Add(GetHash(WillEnqueue.BanArr));
while (Que.Count > 0) {
JyoutaiDef Dequeued = Que.Dequeue();
if (IsClear(Dequeued.BanArr)) {
for (int I = 0; I <= Dequeued.Log.Count - 1; I++) {
Console.WriteLine("{0}手目", I);
Console.WriteLine(Dequeued.Log[I]);
}
break;
}
//下限値枝切り
if (Dequeued.Level + DeriveNeedMinTesuu(Dequeued.BanArr) > LevelLimit) continue;
foreach (char EachPiece in "華琴書茶兄父母祖娘") {
//特殊枝切り 1手目は、華か書を動かす
if (Dequeued.Level == 0 && EachPiece != '華' && EachPiece != '書') continue;
//盤面とピースを引数として、1手後の盤面のListを返す
List<char[,]> MovedArrList = DeriveMovedArrList(Dequeued.BanArr, EachPiece);
foreach (char[,] EachMovedArr in MovedArrList) {
WillEnqueue.BanArr = EachMovedArr;
WillEnqueue.Level = Dequeued.Level + 1;
//再訪防止
if (VisitedSet.Add(GetHash(EachMovedArr)) == false)
continue;
WillEnqueue.Log = new List<string>(Dequeued.Log);
WillEnqueue.Log.Add(BanToStr(WillEnqueue.BanArr));
Que.Enqueue(WillEnqueue);
}
}
}
Console.WriteLine("経過時間={0}", sw.Elapsed);
}
//クリア判定
static bool IsClear(char[,] pBanArr)
{
return pBanArr[1, 4] == '娘' && pBanArr[2, 4] == '娘';
}
//最小の残り手数を返す(下限値枝切り用)
static int DeriveNeedMinTesuu(char[,] pBanArr)
{
if (pBanArr[0, 0] == '娘') return 13;
if (pBanArr[1, 0] == '娘') return 9;
if (pBanArr[2, 0] == '娘') return 13;
if (pBanArr[0, 1] == '娘') return 9;
if (pBanArr[1, 1] == '娘') return 5;
if (pBanArr[2, 1] == '娘') return 9;
if (pBanArr[0, 2] == '娘') return 5;
if (pBanArr[1, 2] == '娘') return 1;
if (pBanArr[2, 2] == '娘') return 5;
if (pBanArr[0, 3] == '娘') return 1;
if (pBanArr[1, 3] == '娘') return 0;
if (pBanArr[2, 3] == '娘') return 1;
return -1;
}
struct MoveInfoDef
{
internal char[,] BanArr;
internal PointDef FromPos;
}
//盤面とピースを引数として、1手後の盤面のListを返す
static List<char[,]> DeriveMovedArrList(char[,] pBanArr, char pPiece)
{
var WillReturn = new List<char[,]>();
PointDef[] PiecePosArr = DerivePiecePosArr(pBanArr, pPiece);
var Stk = new Stack<MoveInfoDef>();
MoveInfoDef WillPush;
foreach (PointDef EachPos in PiecePosArr) {
WillPush.BanArr = pBanArr;
WillPush.FromPos = EachPos;
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);
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 == '母') {
Func<char> Derive2Mojime = () =>
pPiece == '祖' ? pBanArr[FromX, FromY + 1] : '親';
//上に移動
if (IsSpace(pBanArr, FromX, FromY - 1)) {
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[FromX, FromY - 1] = pPiece;
wkArr[FromX, FromY] = Derive2Mojime();
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] = Derive2Mojime();
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] = Derive2Mojime();
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] = Derive2Mojime();
wkArr[FromX, FromY] = wkArr[FromX, FromY + 1] = '□';
AddAct1(wkArr, FromX + 1, FromY);
}
}
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] = '□';
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] = '兄';
wkArr[FromX + 1, FromY + 1] = '弟';
AddAct1(wkArr, FromX, FromY + 1);
}
//左に移動
if (IsSpace(pBanArr, FromX - 1, FromY)) {
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[FromX - 1, FromY] = '兄';
wkArr[FromX, FromY] = '弟';
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] = '兄';
wkArr[FromX + 2, FromY] = '弟';
AddAct1(wkArr, FromX + 1, FromY);
}
}
if (pPiece == '華' || pPiece == '琴' || 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[] DerivePiecePosArr(char[,] pBanArr, char pPiece)
{
var WillReturn = new List<PointDef>();
for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
if (pBanArr[LoopX, LoopY] == pPiece) {
if (pPiece == '父' || pPiece == '母') {
if (LoopY > 0 && pBanArr[LoopX, LoopY - 1] == '祖')
continue;
}
PointDef WillAdd;
WillAdd.X = LoopX;
WillAdd.Y = LoopY;
WillReturn.Add(WillAdd);
//娘は1座標のみ
if (pPiece == '娘')
return WillReturn.ToArray();
}
}
}
return WillReturn.ToArray();
}
//座標が空白かを判定
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 NumList = new List<ulong>();
var sb = new System.Text.StringBuilder();
for (int X = 0; X <= UB_X; X++) {
for (int Y = 0; Y <= UB_Y; Y++) {
char wkChar = pBanArr[X, Y];
if (wkChar == '親') continue;
if (wkChar == '弟') continue;
if (wkChar == '父' || wkChar == '母') {
if (Y > 0 && pBanArr[X, Y - 1] == '祖')
continue;
}
if (wkChar == '娘') NumList.Add(4);
else if (wkChar == '祖') NumList.Add(3);
else if (wkChar == '父') NumList.Add(3);
else if (wkChar == '母') NumList.Add(3);
else if (wkChar == '兄') NumList.Add(2);
else if (wkChar == '華') NumList.Add(1);
else if (wkChar == '琴') NumList.Add(1);
else if (wkChar == '書') NumList.Add(1);
else if (wkChar == '茶') NumList.Add(1);
else NumList.Add(0);
}
}
//5の21乗=476837158203125なので5進数ならオーバーフローしない
ulong WillReturn = 0;
foreach (ulong EachInt in NumList) {
WillReturn *= 5;
WillReturn += EachInt;
}
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();
}
}
