using System;
using System.Collections.Generic;
class Program
{
const int UB = 5;
struct PointDef
{
internal int X;
internal int Y;
}
struct JyoutaiDef
{
internal char[,] BanArr;
internal int Level;
internal List<string> Log;
}
static void Main()
{
string[] InitArr ={"１２２２３□",
"１１２３３３",
"１４４４赤５",
"□６４□５５",
"６６６黄７５",
"□６□７７７"};
var Stk = new Stack<JyoutaiDef>();
JyoutaiDef WillPush;
WillPush.BanArr = new char[UB + 1, UB + 1];
for (int X = 0; X <= UB; X++) {
for (int Y = 0; Y <= UB; 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<string, int>();
MinTesuuDict.Add(GetHash(WillPush.BanArr), 0);
List<string> AnswerLog = null;
while (Stk.Count > 0) {
JyoutaiDef Popped = Stk.Pop();
if (IsClear(Popped.BanArr)) {
AnswerLog = Popped.Log;
continue;
}
foreach (char EachPiece in "１２３４５６７赤黄") {
//盤面とピースを引数として、1手後の盤面のListを返す
List<char[,]> MovedBanArrList = DeriveMovedBanArrList(Popped.BanArr, EachPiece);
foreach (char[,] EachMovedBanArr in MovedBanArrList) {
WillPush.BanArr = EachMovedBanArr;
WillPush.Level = Popped.Level + 1;
//メモ化探索
int MinTesuu;
string Hash = GetHash(EachMovedBanArr);
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 bool IsClear(char[,] pBanArr)
{
if (pBanArr[4, 2] != '黄') return false;
if (pBanArr[3, 4] != '赤') return false;
return true;
}
//盤面とピースを引数として、1手後の盤面のListを返す
static List<char[,]> DeriveMovedBanArrList(char[,] pBanArr, char pPiece)
{
var WillReturn = new List<char[,]>();
var Stk = new Stack<char[,]>();
char[,] WillPush;
WillPush = pBanArr;
Stk.Push(WillPush);
var VisitedSet = new HashSet<string>();
while (Stk.Count > 0) {
char[,] Popped = Stk.Pop();
List<char[,]> MovedBanArrList = DeriveMovedBanArrListHelper(Popped, pPiece);
foreach (char[,] EachBanArr in MovedBanArrList) {
string CurrHash = GetHash(EachBanArr);
if (CurrHash == GetHash(pBanArr)) continue;
if (VisitedSet.Add(CurrHash) == false) continue;
WillReturn.Add(EachBanArr);
Stk.Push(EachBanArr);
}
}
return WillReturn;
}
//盤面とピースを引数として、移動後の盤面のListを返す
static List<char[,]> DeriveMovedBanArrListHelper(char[,] pBanArr, char pPiece)
{
var WillReturn = new List<char[,]>();
PointDef wkPiecePoint = DerivePiecePoint(pBanArr, pPiece);
int CurrX = wkPiecePoint.X;
int CurrY = wkPiecePoint.Y;
if (pPiece == '１') {
//上に移動
if (IsSpace(pBanArr, CurrX, CurrY - 1)
&& IsSpace(pBanArr, CurrX + 1, CurrY)) {
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[CurrX, CurrY - 1] = '１';
wkArr[CurrX + 1, CurrY] = '１';
wkArr[CurrX, CurrY + 2] = '□';
wkArr[CurrX + 1, CurrY + 1] = '□';
WillReturn.Add(wkArr);
}
//下に移動
if (IsSpace(pBanArr, CurrX, CurrY + 3)
&& IsSpace(pBanArr, CurrX + 1, CurrY + 2)) {
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[CurrX, CurrY + 3] = '１';
wkArr[CurrX + 1, CurrY + 2] = '１';
wkArr[CurrX, CurrY] = '□';
wkArr[CurrX + 1, CurrY + 1] = '□';
WillReturn.Add(wkArr);
}
//左に移動
if (IsSpace(pBanArr, CurrX - 1, CurrY)
&& IsSpace(pBanArr, CurrX - 1, CurrY + 1)
&& IsSpace(pBanArr, CurrX - 1, CurrY + 2)) {
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[CurrX - 1, CurrY] = '１';
wkArr[CurrX - 1, CurrY + 1] = '１';
wkArr[CurrX - 1, CurrY + 2] = '１';
wkArr[CurrX, CurrY] = '□';
wkArr[CurrX + 1, CurrY + 1] = '□';
wkArr[CurrX, CurrY + 2] = '□';
WillReturn.Add(wkArr);
}
//右に移動
if (IsSpace(pBanArr, CurrX + 1, CurrY)
&& IsSpace(pBanArr, CurrX + 2, CurrY + 1)
&& IsSpace(pBanArr, CurrX + 1, CurrY + 2)) {
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[CurrX + 1, CurrY] = '１';
wkArr[CurrX + 2, CurrY + 1] = '１';
wkArr[CurrX + 1, CurrY + 2] = '１';
wkArr[CurrX, CurrY] = '□';
wkArr[CurrX, CurrY + 1] = '□';
wkArr[CurrX, CurrY + 2] = '□';
WillReturn.Add(wkArr);
}
}
if (pPiece == '２' || pPiece == '４') {
//上に移動
if (IsSpace(pBanArr, CurrX, CurrY - 1)
&& IsSpace(pBanArr, CurrX + 1, CurrY - 1)
&& IsSpace(pBanArr, CurrX + 2, CurrY - 1)) {
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[CurrX, CurrY - 1] = pPiece;
wkArr[CurrX + 1, CurrY - 1] = pPiece;
wkArr[CurrX + 2, CurrY - 1] = pPiece;
wkArr[CurrX, CurrY] = '□';
wkArr[CurrX + 1, CurrY + 1] = '□';
wkArr[CurrX + 2, CurrY] = '□';
WillReturn.Add(wkArr);
}
//下に移動
if (IsSpace(pBanArr, CurrX, CurrY + 1)
&& IsSpace(pBanArr, CurrX + 1, CurrY + 2)
&& IsSpace(pBanArr, CurrX + 2, CurrY + 1)) {
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[CurrX, CurrY + 1] = pPiece;
wkArr[CurrX + 1, CurrY + 2] = pPiece;
wkArr[CurrX + 2, CurrY + 1] = pPiece;
wkArr[CurrX, CurrY] = '□';
wkArr[CurrX + 1, CurrY] = '□';
wkArr[CurrX + 2, CurrY] = '□';
WillReturn.Add(wkArr);
}
//左に移動
if (IsSpace(pBanArr, CurrX - 1, CurrY)
&& IsSpace(pBanArr, CurrX, CurrY + 1)) {
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[CurrX - 1, CurrY] = pPiece;
wkArr[CurrX, CurrY + 1] = pPiece;
wkArr[CurrX + 2, CurrY] = '□';
wkArr[CurrX + 1, CurrY + 1] = '□';
WillReturn.Add(wkArr);
}
//右に移動
if (IsSpace(pBanArr, CurrX + 3, CurrY)
&& IsSpace(pBanArr, CurrX + 2, CurrY + 1)) {
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[CurrX + 3, CurrY] = pPiece;
wkArr[CurrX + 2, CurrY + 1] = pPiece;
wkArr[CurrX, CurrY] = '□';
wkArr[CurrX + 1, CurrY + 1] = '□';
WillReturn.Add(wkArr);
}
}
if (pPiece == '３' || pPiece == '７') {
//上に移動
if (IsSpace(pBanArr, CurrX - 1, CurrY)
&& IsSpace(pBanArr, CurrX, CurrY - 1)
&& IsSpace(pBanArr, CurrX + 1, CurrY)) {
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[CurrX - 1, CurrY] = pPiece;
wkArr[CurrX, CurrY - 1] = pPiece;
wkArr[CurrX + 1, CurrY] = pPiece;
wkArr[CurrX - 1, CurrY + 1] = '□';
wkArr[CurrX, CurrY + 1] = '□';
wkArr[CurrX + 1, CurrY + 1] = '□';
WillReturn.Add(wkArr);
}
//下に移動
if (IsSpace(pBanArr, CurrX - 1, CurrY + 2)
&& IsSpace(pBanArr, CurrX, CurrY + 2)
&& IsSpace(pBanArr, CurrX + 1, CurrY + 2)) {
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[CurrX - 1, CurrY + 2] = pPiece;
wkArr[CurrX, CurrY + 2] = pPiece;
wkArr[CurrX + 1, CurrY + 2] = pPiece;
wkArr[CurrX - 1, CurrY + 1] = '□';
wkArr[CurrX, CurrY] = '□';
wkArr[CurrX + 1, CurrY + 1] = '□';
WillReturn.Add(wkArr);
}
//左に移動
if (IsSpace(pBanArr, CurrX - 1, CurrY)
&& IsSpace(pBanArr, CurrX - 2, CurrY + 1)) {
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[CurrX - 1, CurrY] = pPiece;
wkArr[CurrX - 2, CurrY + 1] = pPiece;
wkArr[CurrX, CurrY] = '□';
wkArr[CurrX + 1, CurrY + 1] = '□';
WillReturn.Add(wkArr);
}
//右に移動
if (IsSpace(pBanArr, CurrX + 1, CurrY)
&& IsSpace(pBanArr, CurrX + 2, CurrY + 1)) {
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[CurrX + 1, CurrY] = pPiece;
wkArr[CurrX + 2, CurrY + 1] = pPiece;
wkArr[CurrX, CurrY] = '□';
wkArr[CurrX - 1, CurrY + 1] = '□';
WillReturn.Add(wkArr);
}
}
if (pPiece == '５') {
//上に移動
if (IsSpace(pBanArr, CurrX - 1, CurrY)
&& IsSpace(pBanArr, CurrX, CurrY - 1)) {
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[CurrX - 1, CurrY] = '５';
wkArr[CurrX, CurrY - 1] = '５';
wkArr[CurrX - 1, CurrY + 1] = '□';
wkArr[CurrX, CurrY + 2] = '□';
WillReturn.Add(wkArr);
}
//下に移動
if (IsSpace(pBanArr, CurrX - 1, CurrY + 2)
&& IsSpace(pBanArr, CurrX, CurrY + 3)) {
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[CurrX - 1, CurrY + 2] = '５';
wkArr[CurrX, CurrY + 3] = '５';
wkArr[CurrX - 1, CurrY + 1] = '□';
wkArr[CurrX, CurrY] = '□';
WillReturn.Add(wkArr);
}
//左に移動
if (IsSpace(pBanArr, CurrX - 1, CurrY)
&& IsSpace(pBanArr, CurrX, CurrY + 1)
&& IsSpace(pBanArr, CurrX - 1, CurrY + 2)) {
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[CurrX - 1, CurrY] = '５';
wkArr[CurrX - 2, CurrY + 1] = '５';
wkArr[CurrX - 1, CurrY + 2] = '５';
wkArr[CurrX + 1, CurrY] = '□';
wkArr[CurrX + 1, CurrY + 1] = '□';
wkArr[CurrX + 1, CurrY + 2] = '□';
WillReturn.Add(wkArr);
}
//右に移動
if (IsSpace(pBanArr, CurrX + 1, CurrY)
&& IsSpace(pBanArr, CurrX + 1, CurrY + 1)
&& IsSpace(pBanArr, CurrX + 1, CurrY + 2)) {
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[CurrX + 1, CurrY] = '５';
wkArr[CurrX + 1, CurrY + 1] = '５';
wkArr[CurrX + 1, CurrY + 2] = '５';
wkArr[CurrX, CurrY] = '□';
wkArr[CurrX - 1, CurrY + 1] = '□';
wkArr[CurrX, CurrY + 2] = '□';
WillReturn.Add(wkArr);
}
}
if (pPiece == '６') {
//上に移動
if (IsSpace(pBanArr, CurrX - 1, CurrY)
&& IsSpace(pBanArr, CurrX, CurrY - 1)
&& IsSpace(pBanArr, CurrX + 1, CurrY)) {
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[CurrX - 1, CurrY] = '６';
wkArr[CurrX, CurrY - 1] = '６';
wkArr[CurrX + 1, CurrY] = '６';
wkArr[CurrX - 1, CurrY + 1] = '□';
wkArr[CurrX, CurrY + 2] = '□';
wkArr[CurrX + 1, CurrY + 1] = '□';
WillReturn.Add(wkArr);
}
//下に移動
if (IsSpace(pBanArr, CurrX - 1, CurrY + 2)
&& IsSpace(pBanArr, CurrX, CurrY + 3)
&& IsSpace(pBanArr, CurrX + 1, CurrY + 2)) {
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[CurrX - 1, CurrY + 2] = '６';
wkArr[CurrX, CurrY + 3] = '６';
wkArr[CurrX + 1, CurrY + 2] = '６';
wkArr[CurrX - 1, CurrY + 1] = '□';
wkArr[CurrX, CurrY] = '□';
wkArr[CurrX + 1, CurrY + 1] = '□';
WillReturn.Add(wkArr);
}
//左に移動
if (IsSpace(pBanArr, CurrX - 1, CurrY)
&& IsSpace(pBanArr, CurrX - 2, CurrY + 1)
&& IsSpace(pBanArr, CurrX - 1, CurrY + 2)) {
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[CurrX - 1, CurrY] = '６';
wkArr[CurrX - 2, CurrY + 1] = '６';
wkArr[CurrX - 1, CurrY + 2] = '６';
wkArr[CurrX, CurrY] = '□';
wkArr[CurrX + 1, CurrY + 1] = '□';
wkArr[CurrX, CurrY + 2] = '□';
WillReturn.Add(wkArr);
}
//右に移動
if (IsSpace(pBanArr, CurrX + 1, CurrY)
&& IsSpace(pBanArr, CurrX + 2, CurrY + 1)
&& IsSpace(pBanArr, CurrX + 1, CurrY + 2)) {
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[CurrX + 1, CurrY] = '６';
wkArr[CurrX + 2, CurrY + 1] = '６';
wkArr[CurrX + 1, CurrY + 2] = '６';
wkArr[CurrX, CurrY] = '□';
wkArr[CurrX - 1, CurrY + 1] = '□';
wkArr[CurrX, CurrY + 2] = '□';
WillReturn.Add(wkArr);
}
}
if (pPiece == '赤' || pPiece == '黄') {
//上に移動
if (IsSpace(pBanArr, CurrX, CurrY - 1)) {
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[CurrX, CurrY - 1] = pPiece; wkArr[CurrX, CurrY] = '□';
WillReturn.Add(wkArr);
}
//下に移動
if (IsSpace(pBanArr, CurrX, CurrY + 1)) {
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[CurrX, CurrY + 1] = pPiece; wkArr[CurrX, CurrY] = '□';
WillReturn.Add(wkArr);
}
//左に移動
if (IsSpace(pBanArr, CurrX - 1, CurrY)) {
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[CurrX - 1, CurrY] = pPiece; wkArr[CurrX, CurrY] = '□';
WillReturn.Add(wkArr);
}
//右に移動
if (IsSpace(pBanArr, CurrX + 1, CurrY)) {
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[CurrX + 1, CurrY] = pPiece; wkArr[CurrX, CurrY] = '□';
WillReturn.Add(wkArr);
}
}
return WillReturn;
}
//盤面とピースを引数として、ピースの左上の座標を返す
static PointDef DerivePiecePoint(char[,] pBanArr, char pPiece)
{
for (int LoopY = 0; LoopY <= UB; LoopY++) {
for (int LoopX = 0; LoopX <= UB; 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 < pX) return false;
if (pY < 0 || UB < pY) return false;
return pBanArr[pX, pY] == '□';
}
//ハッシュ値を求める
static string GetHash(char[,] pBanArr)
{
var sb = new System.Text.StringBuilder();
for (int X = 0; X <= UB; X++) {
for (int Y = 0; Y <= UB; Y++) {
sb.Append(pBanArr[X, Y]);
}
}
return sb.ToString();
}
//盤面をString型で表現
static string BanToStr(char[,] pBanArr)
{
var sb = new System.Text.StringBuilder();
for (int Y = 0; Y <= UB; Y++) {
for (int X = 0; X <= UB; X++) {
sb.Append(pBanArr[X, Y]);
}
sb.AppendLine();
}
return sb.ToString();
}
}
6個のT字型ピースと1個の十字架型ピース、 それに赤と緑の丸いピース1個ずつ、合計9個のピースで構成されているスライドパズル。 指定のスタート位置にそれぞれピースを置き、赤と黄緑の丸いピースを入れ換えるのが目的です。 タイトルの“88”は88手かかるという意味です。