using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static int mQuestionNo = 1;
static char[,] mQuestionArr; //問題の初期盤面
const int UB = 5 - 1;
//問題を定義
static void QuestionDef()
{
string[] wkStrArr = null;
if (mQuestionNo == 1) {
wkStrArr = new string[] {"緑■□□□",
"□□□□□",
"□□穴□□",
"□□□□□",
"□□■□□"};
}
if (mQuestionNo == 2) {
wkStrArr = new string[] {"緑□■□□",
"緑■■□□",
"青■穴□□",
"青□□□□",
"青□□□□"};
}
if (mQuestionNo == 3) {
wkStrArr = new string[] {"□緑■青□",
"緑青■□□",
"■□穴□□",
"青□□□□",
"□□□□□"};
}
if (mQuestionNo == 4) {
wkStrArr = new string[] {"□□■青青",
"□□□□□",
"□□穴□□",
"□□□□□",
"緑青□□□"};
}
if (mQuestionNo == 5) {
wkStrArr = new string[] {"■青□□□",
"緑□■□□",
"青□穴□□",
"□□■□□",
"□□■□□"};
}
if (mQuestionNo == 6) {
wkStrArr = new string[] {"■■■□□",
"□■■□□",
"□□穴□□",
"□□□□□",
"緑緑□□青"};
}
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];
}
static void Main()
{
//問題を定義
QuestionDef();
//反復深化深さ優先探索で解く
for (int I = 1; I < int.MaxValue; I++) {
Console.WriteLine("深さ制限={0}で深さ優先探索を実行中", I);
if (ExecDFS(I)) break;
}
}
struct JyoutaiDef
{
internal int Level;
internal char[,] BanArr;
internal List<char[,]> Log;
}
//レベル制限を引数として深さ優先探索を行う
static bool ExecDFS(int pLevelMax)
{
var Stk = new Stack<JyoutaiDef>();
JyoutaiDef WillPush;
WillPush.Level = 0;
WillPush.BanArr = mQuestionArr;
WillPush.Log = new List<char[,]>() { WillPush.BanArr };
Stk.Push(WillPush);
//盤面に対する最少手数のDict
var MinTesuuDict = new Dictionary<string, int>();
MinTesuuDict.Add(GetHash(WillPush.BanArr), 0);
while (Stk.Count > 0) {
JyoutaiDef Popped = Stk.Pop();
//PrintBan(Popped.BanArr);
//クリア判定
if (IsClear(Popped.BanArr)) {
Console.WriteLine("解を発見");
for (int I = 0; I <= Popped.Log.Count - 1; I++) {
Console.WriteLine("レベル{0}", I);
PrintBan(Popped.Log[I]);
}
return true;
}
//レベル制限
if (pLevelMax <= Popped.Level) continue;
List<char[,]> MovedBanArrList = DeriveMovedBanArrList(Popped.BanArr);
foreach (char[,] EachBanArr in MovedBanArrList) {
WillPush.Level = Popped.Level + 1;
WillPush.BanArr = EachBanArr;
string CurrHash = GetHash(WillPush.BanArr);
if (MinTesuuDict.ContainsKey(CurrHash)) {
if (MinTesuuDict[CurrHash] <= WillPush.Level)
continue;
}
MinTesuuDict[CurrHash] = WillPush.Level;
WillPush.Log = new List<char[,]>(Popped.Log) { WillPush.BanArr };
Stk.Push(WillPush);
}
}
return false;
}
//クリア判定
static bool IsClear(char[,] pBanArr)
{
for (int X = 0; X <= UB; X++)
for (int Y = 0; Y <= UB; Y++)
if (pBanArr[X, Y] == '緑')
return false;
return true;
}
//移動後の盤情報の配列を返す
static List<char[,]> DeriveMovedBanArrList(char[,] pBanArr)
{
//上に全体移動させる場合
char[,] wkArr1 = (char[,])pBanArr.Clone();
for (int X = 0; X <= UB; X++)
for (int Y = 0; Y <= UB; Y++)
ExecMove(wkArr1, X, Y, 0, -1);
//右に全体移動させる場合
char[,] wkArr2 = (char[,])pBanArr.Clone();
for (int Y = 0; Y <= UB; Y++)
for (int X = UB; 0 <= X; X--)
ExecMove(wkArr2, X, Y, 1, 0);
//下に全体移動させる場合
char[,] wkArr3 = (char[,])pBanArr.Clone();
for (int X = 0; X <= UB; X++)
for (int Y = UB; 0 <= Y; Y--)
ExecMove(wkArr3, X, Y, 0, 1);
//左に全体移動させる場合
char[,] wkArr4 = (char[,])pBanArr.Clone();
for (int Y = 0; Y <= UB; Y++)
for (int X = 0; X <= UB; X++)
ExecMove(wkArr4, X, Y, -1, 0);
int BlueCnt = pBanArr.Cast<char>().Count(A => A == '青');
var WillReturn = new List<char[,]>() { wkArr1, wkArr2, wkArr3, wkArr4 };
WillReturn.RemoveAll(A => A.Cast<char>().Count(B => B == '青') < BlueCnt);
return WillReturn;
}
//ピースの移動処理を行う
static void ExecMove(char[,] pBanArr, int pFromX, int pFromY, int pHeniX, int pHeniY)
{
char MovePiece = pBanArr[pFromX, pFromY];
if (MovePiece == '□' || MovePiece == '■' || MovePiece == '穴') return;
Func<int, int, bool> IsInside = (pX, pY) =>
{
if (pX < 0 || UB < pX) return false;
if (pY < 0 || UB < pY) return false;
return true;
};
int CurrX = pFromX + pHeniX;
int CurrY = pFromY + pHeniY;
if (IsInside(CurrX, CurrY) == false
|| pBanArr[CurrX, CurrY] == '■'
|| pBanArr[CurrX, CurrY] == '緑'
|| pBanArr[CurrX, CurrY] == '青') return;
while (true) {
if (pBanArr[CurrX, CurrY] == '穴') {
pBanArr[pFromX, pFromY] = '□';
break;
}
int NextX = CurrX + pHeniX;
int NextY = CurrY + pHeniY;
//止まる場合
if (IsInside(NextX, NextY) == false
|| pBanArr[NextX, NextY] == '■'
|| pBanArr[NextX, NextY] == '緑'
|| pBanArr[NextX, NextY] == '青') {
pBanArr[pFromX, pFromY] = '□';
pBanArr[CurrX, CurrY] = MovePiece;
break;
}
CurrX = NextX;
CurrY = NextY;
}
}
//盤面をハッシュ値に変換
static string GetHash(char[,] pBanArr)
{
var sb = new System.Text.StringBuilder();
for (int X = 0; X <= UB; X++) {
for (int Y = 0; Y <= UB; Y++) {
char CurrChar = pBanArr[X, Y];
if (CurrChar == '□'
|| CurrChar == '緑' || CurrChar == '青')
sb.Append(CurrChar);
}
}
return sb.ToString();
}
//盤面を出力
static void PrintBan(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();
}
Console.WriteLine(sb.ToString());
}
}
盤の上でコマを滑らせ、 緑色のコマを全て中央の穴に落とせばクリアです。 青色のコマは、中央の穴に落としてはいけません。 Q1 緑■□□□ □□□□□ □□穴□□ □□□□□ □□■□□ Q2 緑□■□□ 緑■■□□ 青■穴□□ 青□□□□ 青□□□□ Q3 □緑■青□ 緑青■□□ ■□穴□□ 青□□□□ □□□□□ Q4 □□■青青 □□□□□ □□穴□□ □□□□□ 緑青□□□ Q5 ■青□□□ 緑□■□□ 青□穴□□ □□■□□ □□■□□ Q6 ■■■□□ □■■□□ □□穴□□ □□□□□ 緑緑□□青