using System;
using System.Collections.Generic;
class Program
{
struct JyoutaiDef
{
internal char[,] Ban;
internal List<char[,]> BanList;
internal HashSet<string> ExistBanSet;
internal List<char> MoveLogList;
}
static void Main()
{
var sw = System.Diagnostics.Stopwatch.StartNew();
JyoutaiDef WillPush;
var wkBan = new char[,]{{'■','■','Ｎ','Ｏ'},
{'Ｏ','Ｆ','Ｆ','□'}};
//X座標とY座標を変換してセット
WillPush.Ban = new char[wkBan.GetLength(1), wkBan.GetLength(0)];
for (int X = 0; X <= WillPush.Ban.GetUpperBound(0); X++) {
for (int Y = 0; Y <= WillPush.Ban.GetUpperBound(1); Y++) {
WillPush.Ban[X, Y] = wkBan[Y, X];
}
}
WillPush.BanList = new List<char[,]>() { WillPush.Ban };
WillPush.ExistBanSet = new HashSet<string>();
IsAlReadyExistBan(WillPush.ExistBanSet, WillPush.Ban);
WillPush.MoveLogList = new List<char>();
var stk = new Stack<JyoutaiDef>();
stk.Push(WillPush);
int AnswerLevel = int.MaxValue;
var AnswerBanList = new List<char[,]>();
var AnswerMoveLogList = new List<char>();
while (stk.Count > 0) {
JyoutaiDef Popped = stk.Pop();
if (AnswerLevel < Popped.MoveLogList.Count) continue;
if (IsOK(Popped.Ban)) {
AnswerLevel = Popped.MoveLogList.Count;
Console.WriteLine("解候補を発見しました。手数={0}", AnswerLevel);
AnswerBanList = Popped.BanList;
AnswerMoveLogList = Popped.MoveLogList;
continue;
}
int SpaceX = 0, SpaceY = 0;
for (int X = 0; X <= Popped.Ban.GetUpperBound(0); X++) {
for (int Y = 0; Y <= Popped.Ban.GetUpperBound(1); Y++) {
if (Popped.Ban[X, Y] == '□') {
SpaceX = X;
SpaceY = Y;
}
}
}
Action<int, int, char> PushSyori = (pFromX, pFromY, pMoveLog) =>
{
//■は上下に分断できない
if (pMoveLog == '↑' || pMoveLog == '↓') {
if (Popped.Ban[pFromX, pFromY] == '■') return;
}
WillPush.Ban = (char[,])Popped.Ban.Clone();
//■は左右に分断できない
if (Popped.Ban[pFromX, pFromY] == '■') {
if (pMoveLog == '→') pFromX--;
if (pMoveLog == '←') pFromX++;
}
WillPush.Ban[SpaceX, SpaceY] = WillPush.Ban[pFromX, pFromY];
WillPush.Ban[pFromX, pFromY] = '□';
WillPush.ExistBanSet = new HashSet<string>(Popped.ExistBanSet);
if (IsAlReadyExistBan(WillPush.ExistBanSet, WillPush.Ban)) return;
WillPush.BanList = new List<char[,]>(Popped.BanList) { WillPush.Ban };
WillPush.MoveLogList = new List<char>(Popped.MoveLogList) { pMoveLog };
stk.Push(WillPush);
};
if (SpaceY > 0) //空白の上の文字を下に移動
PushSyori(SpaceX, SpaceY - 1, '↓');
if (SpaceY < Popped.Ban.GetUpperBound(1)) //空白の下の文字を上に移動
PushSyori(SpaceX, SpaceY + 1, '↑');
if (SpaceX > 0) //空白の左の文字を右に移動
PushSyori(SpaceX - 1, SpaceY, '→');
if (SpaceX < Popped.Ban.GetUpperBound(0)) //空白の右の文字を左に移動
PushSyori(SpaceX + 1, SpaceY, '←');
}
Console.WriteLine("解を発見しました。手数={0}", AnswerLevel);
foreach (var AnyMoveLog in AnswerMoveLogList) Console.Write(AnyMoveLog);
Console.WriteLine(); Console.WriteLine();
Console.WriteLine("盤面の遷移は、");
PrintAnswer(AnswerBanList, AnswerMoveLogList);
}
static bool IsOK(char[,] pBan)
{
var wkBan = new char[,]{{'■','■','Ｏ','Ｎ'},
{'Ｏ','Ｆ','Ｆ','□'}};
//X座標とY座標を変換してチェック
for (int X = 0; X <= pBan.GetUpperBound(0); X++) {
for (int Y = 0; Y <= pBan.GetUpperBound(1); Y++) {
if (pBan[X, Y] != wkBan[Y, X]) return false;
}
}
return true;
}
static bool IsAlReadyExistBan(HashSet<string> pExistBanSet, char[,] pBan)
{
var sb = new System.Text.StringBuilder();
for (int X = 0; X <= pBan.GetUpperBound(0); X++) {
for (int Y = 0; Y <= pBan.GetUpperBound(1); Y++) {
sb.Append(pBan[X, Y]);
}
}
return pExistBanSet.Add(sb.ToString()) == false;
}
static void PrintAnswer(List<char[,]> pBanList, List<char> pMoveLogList)
{
for (int I = 0; I <= pBanList.Count - 1; I++) {
for (int Y = 0; Y <= pBanList[I].GetUpperBound(1); Y++) {
for (int X = 0; X <= pBanList[I].GetUpperBound(0); X++) {
Console.Write(pBanList[I][X, Y]);
}
Console.WriteLine();
}
if (I < pBanList.Count - 1) Console.WriteLine(pMoveLogList[I]);
}
Console.WriteLine();
}
}
Fig.2
