using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static int mQuestionNo = 2;
static char[,] mQuestionArr; //問題の初期盤面
const int UB = 4 - 1;
struct PointDef
{
internal int X;
internal int Y;
}
//問題を定義
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 Tesuu;
internal int Level;
internal char[,] BanArr;
internal PointDef CurrPos;
internal List<char[,]> Log;
}
//手数制限を引数として深さ優先探索を行う
static bool ExecDFS(int pTesuuMax)
{
var Stk = new Stack<JyoutaiDef>();
JyoutaiDef WillPush;
WillPush.Tesuu = 0;
WillPush.Level = 0;
WillPush.BanArr = mQuestionArr;
WillPush.CurrPos = new PointDef() { X = -1, Y = -1 };
WillPush.Log = new List<char[,]>() { WillPush.BanArr };
Stk.Push(WillPush);
int AnswerLevel = int.MaxValue;
List<char[,]> AnswerKouhoLog = null;
bool FoundAnswer = false;
//盤面に対する最少手数のDict
var MinTesuuDict = new Dictionary<string, MinTesuuInfo>();
MinTesuuDict.Add(GetHash(WillPush.BanArr, WillPush.CurrPos),
new MinTesuuInfo() { Tesuu = 0, Level = 0 });
while (Stk.Count > 0) {
JyoutaiDef Popped = Stk.Pop();
//下限値枝切り
if (pTesuuMax < Popped.Tesuu) continue;
if (pTesuuMax == Popped.Tesuu && AnswerLevel <= Popped.Level) continue;
//クリア判定
if (IsClear(Popped.BanArr)) {
if (Popped.Level < AnswerLevel) {
Console.WriteLine("{0}手({1}レベル)の解候補を発見",
Popped.Tesuu, Popped.Level);
AnswerLevel = Popped.Level;
AnswerKouhoLog = Popped.Log;
FoundAnswer = true;
}
continue;
}
for (int LoopX = 0; LoopX <= UB; LoopX++) {
for (int LoopY = 0; LoopY <= UB; LoopY++) {
if (Popped.BanArr[LoopX, LoopY] == '□') continue;
JumpedInfoDef[] JumpedInfoArr =
DeriveJumpedInfoArr(Popped.BanArr, LoopX, LoopY);
foreach (JumpedInfoDef EachJumoedInfo in JumpedInfoArr) {
if (Popped.CurrPos.X != LoopX || Popped.CurrPos.Y != LoopY)
WillPush.Tesuu = Popped.Tesuu + 1;
else WillPush.Tesuu = Popped.Tesuu;
WillPush.Level = Popped.Level + 1;
WillPush.BanArr = EachJumoedInfo.BanArr;
WillPush.CurrPos = EachJumoedInfo.NewCurrPos;
WillPush.Log = new List<char[,]>(Popped.Log) { WillPush.BanArr };
string CurrHash = GetHash(WillPush.BanArr, WillPush.CurrPos);
MinTesuuInfo CurrTesuuInfo;
CurrTesuuInfo.Tesuu = WillPush.Tesuu;
CurrTesuuInfo.Level = WillPush.Level;
if (MinTesuuDict.ContainsKey(CurrHash)) {
if (MinTesuuDict[CurrHash].Tesuu < CurrTesuuInfo.Tesuu)
continue;
if (MinTesuuDict[CurrHash].Tesuu == CurrTesuuInfo.Tesuu
&& MinTesuuDict[CurrHash].Level <= CurrTesuuInfo.Level)
continue;
}
MinTesuuDict[CurrHash] = CurrTesuuInfo;
Stk.Push(WillPush);
}
}
}
}
if (FoundAnswer) {
for (int I = 0; I <= AnswerKouhoLog.Count - 1; I++) {
Console.WriteLine("レベル{0}", I);
PrintBan(AnswerKouhoLog[I]);
}
return true;
}
return false;
}
//クリア判定
static bool IsClear(char[,] pBanArr)
{
for (int LoopX = 0; LoopX <= UB; LoopX++) {
for (int LoopY = 0; LoopY <= UB; LoopY++) {
if (pBanArr[LoopX, LoopY] == '裏') return false;
}
}
return true;
}
//ジャンプ後の盤情報
struct JumpedInfoDef
{
internal char[,] BanArr;
internal PointDef NewCurrPos;
}
//カメのジャンプ後の盤情報の配列を返す
static JumpedInfoDef[] DeriveJumpedInfoArr(char[,] pBanArr, int pFromX, int pFromY)
{
var WillReturn = new List<JumpedInfoDef>();
Func<int, int, bool> IsInside = (pX, pY) =>
{
if (pX < 0 || UB < pX) return false;
if (pY < 0 || UB < pY) return false;
return true;
};
Action<int, int> JumpAct = (pHeniX, pHeniY) =>
{
//1マス先のチェック
if (IsInside(pFromX + pHeniX, pFromY + pHeniY) == false) return;
if (pBanArr[pFromX + pHeniX, pFromY + pHeniY] == '□') return;
//2マス先のチェック
if (IsInside(pFromX + pHeniX * 2, pFromY + pHeniY * 2) == false) return;
if (pBanArr[pFromX + pHeniX * 2, pFromY + pHeniY * 2] == '□') {
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[pFromX, pFromY] = '□';
HantenSyori(wkArr, pFromX + pHeniX, pFromY + pHeniY);
wkArr[pFromX + pHeniX * 2, pFromY + pHeniY * 2] = pBanArr[pFromX, pFromY];
JumpedInfoDef WillAdd;
WillAdd.BanArr = wkArr;
WillAdd.NewCurrPos =
new PointDef() { X = pFromX + pHeniX * 2, Y = pFromY + pHeniY * 2 };
WillReturn.Add(WillAdd);
return;
}
//3マス先のチェック
if (IsInside(pFromX + pHeniX * 3, pFromY + pHeniY * 3) == false) return;
if (pBanArr[pFromX + pHeniX * 3, pFromY + pHeniY * 3] == '□') {
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[pFromX, pFromY] = '□';
HantenSyori(wkArr, pFromX + pHeniX, pFromY + pHeniY);
HantenSyori(wkArr, pFromX + pHeniX * 2, pFromY + pHeniY * 2);
wkArr[pFromX + pHeniX * 3, pFromY + pHeniY * 3] = pBanArr[pFromX, pFromY];
JumpedInfoDef WillAdd;
WillAdd.BanArr = wkArr;
WillAdd.NewCurrPos =
new PointDef() { X = pFromX + pHeniX * 3, Y = pFromY + pHeniY * 3 };
WillReturn.Add(WillAdd);
return;
}
};
JumpAct(-1, -1); JumpAct(-1, 0); JumpAct(-1, 1);
JumpAct(0, -1); JumpAct(0, +1);
JumpAct(1, -1); JumpAct(1, 0); JumpAct(1, -1);
return WillReturn.ToArray();
}
//指定したマスのカメを反転
static void HantenSyori(char[,] pBanArr, int pX, int pY)
{
if (pBanArr[pX, pY] == '表')
pBanArr[pX, pY] = '裏';
else
pBanArr[pX, pY] = '表';
}
struct MinTesuuInfo
{
internal int Tesuu;
internal int Level;
}
//盤面をハッシュ値に変換
static string GetHash(char[,] pBanArr, PointDef pCurrPos)
{
var sb = new System.Text.StringBuilder();
for (int X = 0; X <= UB; X++) {
for (int Y = 0; Y <= UB; Y++) {
sb.Append(pBanArr[X, Y]);
}
}
sb.AppendFormat("{0},{1}", pCurrPos.X, pCurrPos.Y);
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());
}
}
カメは、1匹または2匹のカメを、縦か横か斜め45度に、跳び越して移動できます。 跳び越されたカメは、表裏が反転します。 全てのカメが表になればクリアです。 同じカメが動き続ける限り1手として、最少手数で解きます。 Q1 裏裏□□ □□□裏 □□□□ □□□□ Q2 □裏裏□ 裏裏裏裏 裏裏裏裏 □裏裏□ Q3 □裏裏□ 裏裏□裏 裏□裏裏 □裏裏□ Q4 □裏裏□ 裏□□裏 □裏裏□ □□□□ Q5 裏□裏□ 表表□裏 □裏裏裏 □□表裏 Q6 表裏表裏 裏表裏表 表裏表裏 □表裏表