using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static int mQuestionNo = 7;
static char[,] mQuestionArr = new char[UB + 1, UB + 1]; //問題の初期盤面
static char mRedCar; //赤い車の文字
const int UB = 5;
//問題を定義
static void QuestionDef()
{
string[] wkStrArr = null;
if (mQuestionNo == 1) {
wkStrArr = new string[] {"ＡＢＢ□□□",
"Ａ□□Ｃ□□",
"ＡＤＤＣ□□",
"Ｅ□□Ｃ□Ｆ",
"ＥＧＧ□□Ｆ",
"□□ＨＨＨＦ"};
mRedCar = 'Ｄ';
}
if (mQuestionNo == 2) {
wkStrArr = new string[] {"ＡＡＢＢＣＤ",
"□□ＥＥＣＤ",
"□□ＦＦＧＤ",
"□□Ｈ□Ｇ□",
"□□Ｈ□ＩＩ",
"□□Ｈ□□□"};
mRedCar = 'Ｆ';
}
if (mQuestionNo == 3) {
wkStrArr = new string[] {"Ａ□□ＢＣＣ",
"Ａ□□ＢＤ□",
"□□ＥＥＤ□",
"ＦＦＧＧＤＨ",
"ＩＪＫＫＫＨ",
"ＩＪ□□□Ｈ"};
mRedCar = 'Ｅ';
}
if (mQuestionNo == 4) {
wkStrArr = new string[] {"ＡＡＢ□□Ｃ",
"ＤＤＢ□□Ｃ",
"ＥＥＦ□□Ｃ",
"ＧＨＦＩＩＩ",
"ＧＨ□ＪＫＫ",
"ＧＬＬＪＭＭ"};
mRedCar = 'Ｅ';
}
if (mQuestionNo == 5) {
wkStrArr = new string[] {"ＡＡＢ□□□",
"□□ＢＣ□□",
"ＤＤＥＣＦ□",
"ＧＧＥＨＦ□",
"ＩＪＪＨＦＫ",
"ＩＬＬＬ□Ｋ"};
mRedCar = 'Ｄ';
}
if (mQuestionNo == 6) {
wkStrArr = new string[] {"ＡＢＢＣＣＤ",
"Ａ□ＥＦＦＤ",
"ＧＧＥＨ□□",
"□□□ＨＩＩ",
"ＪＪＪＨＫ□",
"ＬＬＭＭＫ□"};
mRedCar = 'Ｇ';
}
if (mQuestionNo == 7) {
wkStrArr = new string[] {"ＡＡＢ□□□",
"ＣＤＢ□□Ｅ",
"ＣＤＦＦＧＥ",
"ＣＨＨＨＧＩ",
"□□ＪＫＧＩ",
"□□ＪＫＬＬ"};
mRedCar = 'Ｆ';
}
for (int X = 0; X <= UB; X++) {
for (int Y = 0; Y <= UB; Y++) {
mQuestionArr[X, Y] = wkStrArr[Y][X];
}
}
}
struct JyoutaiDef
{
internal char[,] BanArr;
internal int Level;
internal List<string> Log;
}
static void Main()
{
//問題を定義
QuestionDef();
//ピースの配置情報を取得
DerivePieceHeniListDict();
//反復深化深さ優先探索で解く
for (int I = 1; I < int.MaxValue; I++) {
Console.WriteLine("深さ制限={0}で深さ優先探索を実行中", I);
if (ExecDFS(I)) break;
}
}
//レベル制限を引数として深さ優先探索を行う
static bool ExecDFS(int pLevelMax)
{
//車のIDの配列
char[] CarIDArr = mQuestionArr.Cast<char>().Where(A => A != '□').Distinct().ToArray();
Array.Sort<char>(CarIDArr);
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);
var MinTesuuDict = new Dictionary<string, int>();
MinTesuuDict.Add(GetHash(WillPush.BanArr), 0);
bool FoundAnswer = false;
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) {
FoundAnswer = true;
AnswerLog = Popped.Log;
AnswerLevel = Popped.Level;
Console.WriteLine("{0}手の解を発見", Popped.Level);
}
break;
}
//レベル制限
if (pLevelMax <= Popped.Level) continue;
foreach (char EachCarID in CarIDArr) {
MoveInfoDef wkMoveInfo = DeriveMoveInfo(EachCarID, Popped.BanArr);
foreach (PointDef EachHeni in wkMoveInfo.HeniArr) {
WillPush.BanArr = (char[,])Popped.BanArr.Clone();
//移動後の両端の座標を求める
int MovedFromX = wkMoveInfo.FromPos.X + EachHeni.X;
int MovedFromY = wkMoveInfo.FromPos.Y + EachHeni.Y;
int MovedToX = wkMoveInfo.ToPos.X + EachHeni.X;
int MovedToY = wkMoveInfo.ToPos.Y + EachHeni.Y;
//空白に変更するループ
int StaX = Math.Min(MovedFromX, wkMoveInfo.FromPos.X);
int StaY = Math.Min(MovedFromY, wkMoveInfo.FromPos.Y);
int EndX = Math.Max(MovedToX, wkMoveInfo.ToPos.X);
int EndY = Math.Max(MovedToY, wkMoveInfo.ToPos.Y);
for (int X = StaX; X <= EndX; X++) {
for (int Y = StaY; Y <= EndY; Y++) {
WillPush.BanArr[X, Y] = '□';
}
}
//車IDに変更するループ
for (int X = MovedFromX; X <= MovedToX; X++) {
for (int Y = MovedFromY; Y <= MovedToY; Y++) {
WillPush.BanArr[X, Y] = EachCarID;
}
}
WillPush.Level = Popped.Level + 1;
//メモ化探索
int MinTesuu;
string Hash = GetHash(WillPush.BanArr);
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);
}
}
}
if (FoundAnswer) {
for (int I = 0; I <= AnswerLog.Count - 1; I++) {
Console.WriteLine("{0}手目", I);
Console.WriteLine(AnswerLog[I]);
}
}
return FoundAnswer;
}
//ピースの配置情報を取得
static Dictionary<char, List<PointDef>> mPieceHeniListDict = new Dictionary<char, List<PointDef>>();
static void DerivePieceHeniListDict()
{
char[] PieceArr = mQuestionArr.Cast<char>().Where(X => X != '□').Distinct().ToArray();
Array.Sort(PieceArr);
foreach (char EachPiece in PieceArr) {
bool FirstFlag = true;
PointDef GentenPos = new PointDef() { X = -1, Y = -1 };
for (int LoopY = 0; LoopY <= UB; LoopY++) {
for (int LoopX = 0; LoopX <= UB; LoopX++) {
if (mQuestionArr[LoopX, LoopY] != EachPiece) continue;
if (FirstFlag) {
FirstFlag = false;
GentenPos.X = LoopX;
GentenPos.Y = LoopY;
mPieceHeniListDict.Add(EachPiece, new List<PointDef>());
}
//原点 + 変位ベクトル = カレント座標
//を移項
PointDef HeniVect;
HeniVect.X = LoopX - GentenPos.X;
HeniVect.Y = LoopY - GentenPos.Y;
mPieceHeniListDict[EachPiece].Add(HeniVect);
}
}
}
}
//クリア判定
static bool IsClear(char[,] pBanArr)
{
return pBanArr[4, 2] == mRedCar && pBanArr[5, 2] == mRedCar;
}
struct PointDef
{
internal int X;
internal int Y;
}
//車の移動情報
struct MoveInfoDef
{
internal PointDef FromPos; //両端の開始座標
internal PointDef ToPos; //両端の終了座標
internal PointDef[] HeniArr; //移動変位の配列
}
//車のIDを引数として、車の移動情報を返す
static MoveInfoDef DeriveMoveInfo(char pCarID, char[,] pBanArr)
{
MoveInfoDef MoveInfo = new MoveInfoDef();
bool CanMoveYoko = DeriveCanMoveYoko(pCarID);
bool WillBreak = false;
for (int LoopX = 0; LoopX <= UB; LoopX++) {
for (int LoopY = 0; LoopY <= UB; LoopY++) {
if (pBanArr[LoopX, LoopY] != pCarID) continue;
MoveInfo.FromPos = new PointDef() { X = LoopX, Y = LoopY };
int CarLength = DeriveCarLength(pCarID);
if (CanMoveYoko)
MoveInfo.ToPos = new PointDef() { X = LoopX + CarLength - 1, Y = LoopY };
else MoveInfo.ToPos = new PointDef() { X = LoopX, Y = LoopY + CarLength - 1 };
WillBreak = true;
break;
}
if (WillBreak) break;
}
var HeniList = new List<PointDef>();
Func<int, int, bool> AddFunc = (pI, pBasePos) =>
{
if (pBasePos + pI > UB) return false;
if (pBasePos + pI < 0) return false;
if (CanMoveYoko) {
if (pBanArr[pBasePos + pI, MoveInfo.FromPos.Y] != '□') return false;
HeniList.Add(new PointDef() { X = pI, Y = 0 });
}
else {
if (pBanArr[MoveInfo.FromPos.X, pBasePos + pI] != '□') return false;
HeniList.Add(new PointDef() { X = 0, Y = pI });
}
return true;
};
//変位が正の場合
for (int I = 1; I <= UB; I++) {
if (AddFunc(I, CanMoveYoko ? MoveInfo.ToPos.X : MoveInfo.ToPos.Y) == false)
break;
}
//変位が負の場合
for (int I = -1; I >= -UB; I--) {
if (AddFunc(I, CanMoveYoko ? MoveInfo.FromPos.X : MoveInfo.FromPos.Y) == false)
break;
}
MoveInfo.HeniArr = HeniList.ToArray();
return MoveInfo;
}
//車が横に移動可かを返す
static bool DeriveCanMoveYoko(char pCarID)
{
return mPieceHeniListDict[pCarID][0].X != mPieceHeniListDict[pCarID][1].X;
}
//車の長さを返す
static int DeriveCarLength(char pCarID)
{
return mPieceHeniListDict[pCarID].Count;
}
//盤面をハッシュ値に変換
static string GetHash(char[,] pBanArr)
{
var sb = new System.Text.StringBuilder();
var AppearedSet = new HashSet<char>();
for (int X = 0; X <= UB; X++) {
for (int Y = 0; Y <= UB; Y++) {
char CurrChar = pBanArr[X, Y];
if (CurrChar == '□') sb.Append(CurrChar);
else if (AppearedSet.Add(CurrChar)) sb.Append(CurrChar);
}
}
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();
}
}
