using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static int mQuestionNo = 1;
static char[,] mQuestionArr; //問題の初期盤面
static PointDef mStaPos;
static List<PointDef> mCratePosList = new List<PointDef>();
const int UB = 5;
struct PointDef
{
internal int X;
internal int Y;
}
//問題を定義
static void QuestionDef()
{
string[] wkStrArr = null;
if (mQuestionNo == 1) {
wkStrArr = new string[] {"□□□□□□",
"緑□□□□青",
"□□□□□黄",
"□□□□□□",
"□□□□□□",
"黄□□赤□□"};
mStaPos.X = 5; mStaPos.Y = 1;
}
if (mQuestionNo == 2) {
wkStrArr = new string[] {"□□□□□□",
"□黄□□□□",
"赤□□□□□",
"□黄緑□□□",
"□緑□□□□",
"□□□□□□"};
mStaPos.X = 1; mStaPos.Y = 3;
}
if (mQuestionNo == 3) {
wkStrArr = new string[] {"□□□□□□",
"□□□□□□",
"□□□□□□",
"□□黄緑□赤",
"□青黄□□□",
"□□□□青□"};
mStaPos.X = 1; mStaPos.Y = 4;
}
if (mQuestionNo == 4) {
wkStrArr = new string[] {"□□□□□□",
"□青□黄□□",
"赤□黄青黄□",
"□黄黄□□□",
"□□□□□□",
"□□□黄黄□"};
mStaPos.X = 2; mStaPos.Y = 3;
}
if (mQuestionNo == 5) {
wkStrArr = new string[] {"青□□□□□",
"緑緑□□□□",
"黄黄□□緑□",
"□黄□□□□",
"□□□□□青",
"□赤□□□□"};
mStaPos.X = 0; mStaPos.Y = 2;
}
if (mQuestionNo == 6) {
wkStrArr = new string[] {"□□□□□□",
"□緑□□□□",
"黄緑□□□□",
"黄緑黄黄□□",
"□□□黄黄青",
"赤□□□□□"};
mStaPos.X = 3; mStaPos.Y = 3;
}
if (mQuestionNo == 7) {
wkStrArr = new string[] {"□□黄□□□",
"□黄□黄□□",
"□□□黄黄黄",
"□黄黄□□黄",
"赤□緑□□□",
"□黄□□□□"};
mStaPos.X = 2; mStaPos.Y = 0;
}
if (mQuestionNo == 8) {
wkStrArr = new string[] {"□黄□黄□□",
"□□□□黄□",
"□□黄□□□",
"□黄黄黄黄□",
"青黄□□□赤",
"□□□□黄□"};
mStaPos.X = 1; mStaPos.Y = 4;
}
mQuestionArr = new char[UB + 1, UB + 1];
for (int Y = 0; Y <= UB; Y++)
for (int X = 0; X <= UB; X++)
mQuestionArr[Y, X] = wkStrArr[X][Y];
for (int X = 0; X <= UB; X++) {
for (int Y = 0; Y <= UB; Y++) {
if (mQuestionArr[X, Y] == '□') continue;
PointDef WillAdd;
WillAdd.X = X;
WillAdd.Y = Y;
mCratePosList.Add(WillAdd);
}
}
}
struct JyoutaiDef
{
internal int Level;
internal char[,] BanArr;
internal PointDef CurrPos;
internal List<string> Log;
}
static void Main()
{
//問題を定義
QuestionDef();
var Stk = new Stack<JyoutaiDef>();
JyoutaiDef WillPush;
WillPush.Level = 0;
WillPush.BanArr = mQuestionArr;
WillPush.CurrPos = mStaPos;
WillPush.Log = new List<string>() { BanToStr(WillPush.BanArr, WillPush.CurrPos) };
Stk.Push(WillPush);
int AnswerLevel = int.MaxValue;
List<string> AnswerLog = null;
while (Stk.Count > 0) {
JyoutaiDef Popped = Stk.Pop();
//移動可能な座標のListを返す
List<PointDef> CanMovePosList = DeriveCanMovePosList(Popped.BanArr, Popped.CurrPos);
if (IsClear(Popped.BanArr, CanMovePosList)) {
if (Popped.Level < AnswerLevel) {
AnswerLevel = Popped.Level;
AnswerLog = Popped.Log;
}
continue;
}
//下限値枝切り
if (AnswerLevel <= Popped.Level) continue;
foreach (PointDef EachCanMovePos in CanMovePosList) {
int MovedX = EachCanMovePos.X;
int MovedY = EachCanMovePos.Y;
//移動先が倒せるクレートでない場合
int CrateInd = mCratePosList.FindIndex(A => A.X == MovedX && A.Y == MovedY);
if (CrateInd == -1) continue;
if (Popped.BanArr[MovedX, MovedY] == '■') continue;
int CrateLength = 0;
char CrateColor = Popped.BanArr[MovedX, MovedY];
if (CrateColor == '青') CrateLength = 4;
if (CrateColor == '緑') CrateLength = 3;
if (CrateColor == '黄') CrateLength = 2;
Action<int, int> TaosuAct = (pHeniX, pHeniY) =>
{
char[,] wkArr = (char[,])Popped.BanArr.Clone();
for (int I = 1; I <= CrateLength; I++) {
int CurrX = MovedX + pHeniX * I;
int CurrY = MovedY + pHeniY * I;
if (CurrX < 0 || UB < CurrX) return;
if (CurrY < 0 || UB < CurrY) return;
//空欄でない場合
if (Popped.BanArr[CurrX, CurrY] != '□') return;
wkArr[CurrX, CurrY] = '■';
}
wkArr[MovedX, MovedY] = '□';
WillPush.Level = Popped.Level + 1;
WillPush.BanArr = wkArr;
PointDef wkPos;
wkPos.X = MovedX + pHeniX * CrateLength;
wkPos.Y = MovedY + pHeniY * CrateLength;
WillPush.CurrPos = wkPos;
WillPush.Log = new List<string>(Popped.Log);
WillPush.Log.Add(BanToStr(WillPush.BanArr, WillPush.CurrPos));
Stk.Push(WillPush);
};
TaosuAct(0, -1);
TaosuAct(0, +1);
TaosuAct(-1, 0);
TaosuAct(+1, 0);
}
}
for (int I = 0; I <= AnswerLog.Count - 1; I++) {
Console.WriteLine("レベル{0}", I);
Console.WriteLine(AnswerLog[I]);
}
}
//移動可能な座標のListを返す
static List<PointDef> DeriveCanMovePosList(char[,] pBanArr, PointDef pCurrPos)
{
var WillReturn = new List<PointDef>() { pCurrPos };
var Stk = new Stack<PointDef>();
Stk.Push(pCurrPos);
var VisitedSet = new HashSet<string>();
VisitedSet.Add(string.Format("({0},{1})", pCurrPos.X, pCurrPos.Y));
while (Stk.Count > 0) {
PointDef Popped = Stk.Pop();
Action<int, int> PushSyori = (pNewX, pNewY) =>
{
if (pNewX < 0 || UB < pNewX) return;
if (pNewY < 0 || UB < pNewY) return;
//空欄は訪問不可
if (pBanArr[pNewX, pNewY] == '□') return;
//再訪防止
string wkStr = string.Format("({0},{1})", pNewX, pNewY);
if (VisitedSet.Add(wkStr) == false) return;
PointDef wkPos = new PointDef() { X = pNewX, Y = pNewY };
WillReturn.Add(wkPos);
Stk.Push(wkPos);
};
PushSyori(Popped.X, Popped.Y - 1);
PushSyori(Popped.X, Popped.Y + 1);
PushSyori(Popped.X - 1, Popped.Y);
PushSyori(Popped.X + 1, Popped.Y);
}
return WillReturn;
}
//クリア判定
static bool IsClear(char[,] pBanArr, List<PointDef> pCanMovePosList)
{
for (int X = 0; X <= UB; X++) {
for (int Y = 0; Y <= UB; Y++) {
if (mQuestionArr[X, Y] != '赤') continue;
return pCanMovePosList.Exists(A => A.X == X && A.Y == Y);
}
}
return false;
}
//盤面をString型に変換
static string BanToStr(char[,] pBanArr, PointDef pCurrPos)
{
var sb = new System.Text.StringBuilder();
int CurrX = pCurrPos.X;
int CurrY = pCurrPos.Y;
sb.AppendFormat("Tipperは、[{0},{1}]に存在", CurrX, CurrY);
sb.AppendLine();
for (int Y = 0; Y <= UB; Y++) {
for (int X = 0; X <= UB; X++) {
sb.Append(pBanArr[X, Y]);
}
sb.AppendLine();
}
return sb.ToString();
}
}
Tipperは、クレートを上下左右のいずれかの方向に倒すことができます。 青クレートは倒すと4マス。 緑クレートは倒すと3マス。 黄クレートは倒すと2マス。 になります。 Tipperは、クレート(倒したクレートを含む)の上を移動することができます。 Tipperが、赤クレートに到達すればクリアです。 Q01 初期位置は、[5,1]の青マス □□□□□□ 緑□□□□青 □□□□□黄 □□□□□□ □□□□□□ 黄□□赤□□ Q02 (Beginnerの1) 初期位置は、[1,3]の黄マス □□□□□□ □黄□□□□ 赤□□□□□ □黄緑□□□ □緑□□□□ □□□□□□ Q03 (Intermediateの1) 初期位置は、[1,4]の青マス □□□□□□ □□□□□□ □□□□□□ □□黄緑□赤 □青黄□□□ □□□□青□ Q04 (Advancedの1) 初期位置は、[2,3]の黄マス □□□□□□ □青□黄□□ 赤□黄青黄□ □黄黄□□□ □□□□□□ □□□黄黄□ Q05 (Expertの1) 初期位置は、[0,2]の黄マス 青□□□□□ 緑緑□□□□ 黄黄□□緑□ □黄□□□□ □□□□□青 □赤□□□□ Q06 (Expertの2) 初期位置は、[3,3]の黄マス □□□□□□ □緑□□□□ 黄緑□□□□ 黄緑黄黄□□ □□□黄黄青 赤□□□□□ Q07 (Expertの3) 初期位置は、[2,0]の黄マス □□黄□□□ □黄□黄□□ □□□黄黄黄 □黄黄□□黄 赤□緑□□□ □黄□□□□ Q08 (Expertの4) 初期位置は、[1,4]の黄マス □黄□黄□□ □□□□黄□ □□黄□□□ □黄黄黄黄□ 青黄□□□赤 □□□□黄□