using System;
using System.Collections.Generic;
class Program
{
const int UB_X = 4;
const int UB_Y = 1;
static char[,] mQuestionArr = new char[UB_X + 1, UB_Y + 1]; //問題の初期盤面
//問題を定義
static void QuestionDef()
{
string[] wkArr ={"□くぎょう",
"なんぎょう"};
for (int X = 0; X <= UB_X; X++) {
for (int Y = 0; Y <= UB_Y; Y++) {
mQuestionArr[X, Y] = wkArr[Y][X];
}
}
}
struct JyoutaiDef
{
internal char[,] BanArr;
internal int Level;
internal List<string> Log;
}
static void Main()
{
//問題を定義
QuestionDef();
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);
//盤面に対する最少手数のDict
var MinTesuuDict = new Dictionary<string, 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;
//空きマスを求める
int X = 0, Y = 0;
while (Popped.BanArr[X, Y] != '□') {
if (++X > UB_X) {
Y++; X = 0;
}
}
Action<int, int> PushSyori = (pFromX, pFromY) =>
{
WillPush.BanArr = (char[,])Popped.BanArr.Clone();
WillPush.BanArr[X, Y] = WillPush.BanArr[pFromX, pFromY];
WillPush.BanArr[pFromX, pFromY] = '□';
WillPush.Level = Popped.Level + 1;
int HeniX = X - pFromX;
//「ぎ」の左移動は、「ょ」が連動する
if (HeniX == -1 && Popped.BanArr[pFromX, pFromY] == 'ぎ') {
WillPush.BanArr[pFromX, pFromY] = 'ょ';
WillPush.BanArr[pFromX - HeniX, pFromY] = '□';
}
//「ょ」の右移動は、「ぎ」が連動する
if (HeniX == 1 && Popped.BanArr[pFromX, pFromY] == 'ょ') {
WillPush.BanArr[pFromX, pFromY] = 'ぎ';
WillPush.BanArr[pFromX - HeniX, pFromY] = '□';
}
//当該盤面に、少ない手数か等しい手数で、到達済なら枝切り
string Hash = GetHash(WillPush.BanArr);
int MinTesuu;
if (MinTesuuDict.TryGetValue(Hash, out MinTesuu)) {
if (MinTesuu <= WillPush.Level) return;
}
MinTesuuDict[Hash] = WillPush.Level;
WillPush.Log = new List<string>(Popped.Log);
WillPush.Log.Add(BanToStr(WillPush.BanArr));
Stk.Push(WillPush);
};
//左の数字を、右に移動
if (X > 0) PushSyori(X - 1, Y);
//右の数字を、左に移動
if (X < UB_X) PushSyori(X + 1, Y);
//上の数字を、下に移動
if (Y > 0 && Popped.BanArr[X, Y - 1] != 'ぎ'
&& Popped.BanArr[X, Y - 1] != 'ょ')
PushSyori(X, Y - 1);
//下の数字を、上に移動
if (Y < UB_Y && Popped.BanArr[X, Y + 1] != 'ぎ'
&& Popped.BanArr[X, Y + 1] != 'ょ')
PushSyori(X, Y + 1);
}
for (int I = 0; I <= AnswerLog.Count - 1; I++) {
Console.WriteLine("{0}手目", I);
Console.WriteLine(AnswerLog[I]);
}
}
//クリア判定
static bool IsClear(char[,] pBanArr)
{
if (pBanArr[0, 0] != 'な') return false;
if (pBanArr[1, 0] != 'ん') return false;
if (pBanArr[2, 0] != 'ぎ') return false;
if (pBanArr[4, 0] != 'う') return false;
if (pBanArr[1, 1] != 'く') return false;
if (pBanArr[2, 1] != 'ぎ') return false;
if (pBanArr[4, 1] != 'う') return false;
return true;
}
//最小の残り手数を返す(下限値枝切り用)
static int DeriveNeedMinTesuu(char[,] pBanArr)
{
int WillReturn = 0;
for (int X = 0; X <= UB_X; X++) {
for (int Y = 0; Y <= UB_Y; Y++) {
if (pBanArr[X, Y] == 'な') {
WillReturn += DeriveKyori(X, Y, 0, 0);
}
if (pBanArr[X, Y] == 'ん') {
WillReturn += DeriveKyori(X, Y, 1, 0);
}
if (pBanArr[X, Y] == 'ぎ') {
int Kyori1 = DeriveKyori(X, Y, 2, 0);
int Kyori2 = DeriveKyori(X, Y, 2, 1);
WillReturn += Math.Min(Kyori1, Kyori2);
}
if (pBanArr[X, Y] == 'う') {
int Kyori1 = DeriveKyori(X, Y, 4, 0);
int Kyori2 = DeriveKyori(X, Y, 4, 1);
WillReturn += Math.Min(Kyori1, Kyori2);
}
if (pBanArr[X, Y] == 'く') {
WillReturn += DeriveKyori(X, Y, 1, 1);
}
}
}
return WillReturn;
}
//2点間のマンハッタン距離を求める
static int DeriveKyori(int pX1, int pY1, int pX2, int pY2)
{
return Math.Abs(pX1 - pX2) + Math.Abs(pY1 - pY2);
}
//ハッシュ値を求める
static string GetHash(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]);
}
}
return sb.ToString();
}
//盤面を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();
}
}
各ピースをスライドさせて 下記にすればクリアです。 なんぎょう □くぎょう 「ぎ」と「ょ」はくっついてます。 最少手数は、123手です。