using System;
using System.Collections.Generic;
class Program
{
const int UB_X = 3;
const int UB_Y = 1;
static char[,] mQuestionArr = new char[UB_X + 1, UB_Y + 1]; //問題の初期盤面
//問題を定義
static void QuestionDef()
{
string[] wkArr ={"3421",
"0765"};
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<int, 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] != '0') {
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] = '0';
WillPush.Level = Popped.Level + 1;
int HeniX = X - pFromX;
//3の左移動は、4が連動する
if (HeniX == -1 && Popped.BanArr[pFromX, pFromY] == '3') {
WillPush.BanArr[pFromX, pFromY] = '4';
WillPush.BanArr[pFromX - HeniX, pFromY] = '0';
}
//4の右移動は、3が連動する
if (HeniX == 1 && Popped.BanArr[pFromX, pFromY] == '4') {
WillPush.BanArr[pFromX, pFromY] = '3';
WillPush.BanArr[pFromX - HeniX, pFromY] = '0';
}
//当該盤面に、少ない手数か等しい手数で、到達済なら枝切り
int 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] != '3'
&& Popped.BanArr[X, Y - 1] != '4'
&& Popped.BanArr[X, Y - 1] != '5') {
PushSyori(X, Y - 1);
}
//下の数字を、上に移動
if (Y < UB_Y && Popped.BanArr[X, Y + 1] != '3'
&& Popped.BanArr[X, Y + 1] != '4'
&& Popped.BanArr[X, Y + 1] != '5') {
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)
{
int Hash = GetHash(pBanArr);
if (Hash == 12345670) return true;
return false;
}
//最小の残り手数を返す(下限値枝切り用)
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] == '1')
WillReturn += DeriveKyori(X, Y, 0, 0);
if (pBanArr[X, Y] == '2')
WillReturn += DeriveKyori(X, Y, 1, 0);
if (pBanArr[X, Y] == '3')
WillReturn += DeriveKyori(X, Y, 2, 0);
if (pBanArr[X, Y] == '5')
WillReturn += DeriveKyori(X, Y, 0, 1);
if (pBanArr[X, Y] == '6')
WillReturn += DeriveKyori(X, Y, 1, 1);
if (pBanArr[X, Y] == '7')
WillReturn += DeriveKyori(X, Y, 2, 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 int 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]);
}
}
//Int型ならオーバーフローしない
return int.Parse(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();
}
}