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[] {"○○○○",
"緑○緑赤",
"青緑○緑",
"○○○○"};
}
if (mQuestionNo == 7) {
wkStrArr = new string[] {"○緑○○",
"緑○緑赤",
"青○緑○",
"○○青○"};
}
if (mQuestionNo == 8) {
wkStrArr = new string[] {"○○○緑",
"○赤緑青",
"○○青緑",
"青○○○"};
}
if (mQuestionNo == 9) {
wkStrArr = new string[] {"○青○○",
"○緑○青",
"○赤緑○",
"青緑青緑"};
}
if (mQuestionNo == 10) {
wkStrArr = new string[] {"○青○○",
"青緑緑○",
"緑青○緑",
"青○赤○"};
}
if (mQuestionNo == 11) {
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)
{
return pBanArr[0, 0] == '赤';
}
//ジャンプ後の盤情報
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] = '○';
wkArr[pFromX + pHeniX * 2, pFromY + pHeniY * 2] = pBanArr[pFromX, pFromY];
if (IsValid(wkArr, pFromX + pHeniX * 2, pFromY + pHeniY * 2) == false)
return;
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] = '○';
wkArr[pFromX + pHeniX * 3, pFromY + pHeniY * 3] = pBanArr[pFromX, pFromY];
if (IsValid(wkArr, pFromX + pHeniX * 3, pFromY + pHeniY * 3) == false)
return;
JumpedInfoDef WillAdd;
WillAdd.BanArr = wkArr;
WillAdd.NewCurrPos =
new PointDef() { X = pFromX + pHeniX * 3, Y = pFromY + pHeniY * 3 };
WillReturn.Add(WillAdd);
return;
}
};
JumpAct(0, -1);
JumpAct(0, +1);
JumpAct(+1, 0);
JumpAct(-1, 0);
return WillReturn.ToArray();
}
//移動先の座標を引数として、有効な盤面かを判定
static bool IsValid(char[,] pBanArr, int pCurrX, int pCurrY)
{
Func<int, int, bool> IsRedOrBlue = (pX, pY) =>
{
if (pX < 0 || UB < pX) return false;
if (pY < 0 || UB < pY) return false;
return pBanArr[pX, pY] == '赤'
|| pBanArr[pX, pY] == '青';
};
if (IsRedOrBlue(pCurrX, pCurrY) == false) return true;
if (IsRedOrBlue(pCurrX, pCurrY - 1)) return false;
if (IsRedOrBlue(pCurrX, pCurrY + 1)) return false;
if (IsRedOrBlue(pCurrX - 1, pCurrY)) return false;
if (IsRedOrBlue(pCurrX + 1, pCurrY)) return false;
return true;
}
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匹のロボットを、縦か横に、跳び越して移動できます。 青および赤の大型ロボット同士は上下左右に隣接できません。 赤いロボットが左上のホットスポットに到着すればクリアです。 同じロボットが動き続ける限り1手として、最少手数で解きます。 Q01 ○○○○ ○○○○ 赤○○○ 緑○○○ Q02 ○緑緑赤 青○○○ ○○緑緑 ○○○○ Q03 ○○○○ ○青緑緑 ○○青緑 ○○○赤 Q04 ○青○緑 ○○青○ 赤○○青 ○青緑緑 Q05 (追加問題の41) ○青○○ ○緑赤○ 緑○○○ ○緑○緑 Q06 (追加問題の45) ○○○○ 緑○緑赤 青緑○緑 ○○○○ Q07 (追加問題の49) ○緑○○ 緑○緑赤 青○緑○ ○○青○ Q08 (追加問題の53) ○○○緑 ○赤緑青 ○○青緑 青○○○ Q09 (追加問題の54) ○青○○ ○緑○青 ○赤緑○ 青緑青緑 Q10 (追加問題の55) ○青○○ 青緑緑○ 緑青○緑 青○赤○ Q11 (追加問題の56) 青○○○ ○緑緑青 ○緑○○ ○青○赤