using System;
using System.Collections.Generic;
class Program
{
static int mQuestionNo = 1;
static char[,] mQuestionArr; //問題の初期盤面
const int UB = 5 - 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[] {"○ 緑 緑",
" 緑 緑 ",
"緑 ○ ○",
" 緑 緑 ",
"緑 緑 緑"};
}
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];
}
struct JyoutaiDef
{
internal int Level;
internal char[,] BanArr;
internal PointDef CurrPos;
internal List<char[,]> Log;
}
static void Main()
{
//問題を定義
QuestionDef();
var Stk = new Stack<JyoutaiDef>();
JyoutaiDef WillPush;
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;
while (Stk.Count > 0) {
JyoutaiDef Popped = Stk.Pop();
//クリア判定
if (IsClear(Popped.BanArr)) {
if (Popped.Level < AnswerLevel) {
AnswerLevel = Popped.Level;
Console.WriteLine("{0}手の解候補を発見", Popped.Level);
for (int I = 0; I <= Popped.Log.Count - 1; I++) {
Console.WriteLine("レベル{0}", I);
PrintBan(Popped.Log[I]);
}
}
continue;
}
//下限値枝切り
if (AnswerLevel <= Popped.Level) continue;
for (int LoopX = 0; LoopX <= UB; LoopX++) {
for (int LoopY = 0; LoopY <= UB; LoopY++) {
if (Popped.BanArr[LoopX, LoopY] != '緑'
&& 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.Level = Popped.Level + 1;
else WillPush.Level = Popped.Level;
WillPush.BanArr = EachJumoedInfo.BanArr;
WillPush.CurrPos = EachJumoedInfo.NewCurrPos;
WillPush.Log = new List<char[,]>(Popped.Log) { WillPush.BanArr };
Stk.Push(WillPush);
}
}
}
}
}
//クリア判定
static bool IsClear(char[,] pBanArr)
{
int KaeruCnt = 0;
for (int LoopX = 0; LoopX <= UB; LoopX++) {
for (int LoopY = 0; LoopY <= UB; LoopY++) {
if (pBanArr[LoopX, LoopY] == '緑') KaeruCnt++;
if (pBanArr[LoopX, LoopY] == '赤') KaeruCnt++;
}
}
return KaeruCnt == 1;
}
//ジャンプ後の盤情報
struct JumpedInfoDef
{
internal char[,] BanArr;
internal PointDef NewCurrPos;
}
//カエルのジャンプ後の盤情報の配列を返す
static JumpedInfoDef[] DeriveJumpedInfoArr(char[,] pBanArr, int pFromX, int pFromY)
{
var WillReturn = new List<JumpedInfoDef>();
Action<int, int> JumpAct = (pHeniX, pHeniY) =>
{
if (CanJump(pBanArr, pFromX, pFromY, pHeniX, pHeniY) == false)
return;
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[pFromX, pFromY] = '○';
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);
};
if (pFromX == 0 && pFromY == 0) { //Aからジャンプする場合
JumpAct(0, 2);
JumpAct(1, 1);
JumpAct(2, 0);
}
if (pFromX == 2 && pFromY == 0) { //Bからジャンプする場合
JumpAct(-1, 1);
JumpAct(0, 2);
JumpAct(1, 1);
}
if (pFromX == 4 && pFromY == 0) { //Cからジャンプする場合
JumpAct(-1, 1);
JumpAct(0, 2);
}
if (pFromX == 1 && pFromY == 1) { //Dからジャンプする場合
JumpAct(1, 1);
}
if (pFromX == 3 && pFromY == 1) { //Eからジャンプする場合
JumpAct(-1, 1);
}
if (pFromX == 0 && pFromY == 2) { //Fからジャンプする場合
JumpAct(1, -1);
JumpAct(2, 0);
JumpAct(1, 1);
}
if (pFromX == 2 && pFromY == 2) { //Gからジャンプする場合
JumpAct(-1, -1);
JumpAct(1, -1);
JumpAct(-1, 1);
JumpAct(1, 1);
}
if (pFromX == 4 && pFromY == 2) { //Hからジャンプする場合
JumpAct(-1, -1);
JumpAct(-2, 0);
JumpAct(-1, 1);
}
if (pFromX == 1 && pFromY == 3) { //Iからジャンプする場合
JumpAct(1, -1);
}
if (pFromX == 3 && pFromY == 3) { //Jからジャンプする場合
JumpAct(-1, -1);
}
if (pFromX == 0 && pFromY == 4) { //Kからジャンプする場合
JumpAct(0, -2);
JumpAct(1, -1);
JumpAct(2, 0);
}
if (pFromX == 2 && pFromY == 4) { //Lからジャンプする場合
JumpAct(-1, -1);
JumpAct(0, -2);
JumpAct(1, -1);
}
if (pFromX == 4 && pFromY == 4) { //Mからジャンプする場合
JumpAct(0, -2);
JumpAct(-1, -1);
JumpAct(-2, 0);
}
return WillReturn.ToArray();
}
//カエルがジャンプできるかを判定
static bool CanJump(char[,] pBanArr, int pFromX, int pFromY, int pHeniX, int pHeniY)
{
if (pBanArr[pFromX + pHeniX, pFromY + pHeniY] != '緑') return false;
if (pBanArr[pFromX + pHeniX * 2, pFromY + pHeniY * 2] != '○') return false;
return true;
}
//盤面を出力
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());
}
}
カエルは、縦か横か斜め45度に、1匹のカエルを跳び越して移動します。 跳び越されたカエルは、盤上から取り去ります。 赤カエルだけが残ればクリアです。 (赤カエルがいない問題では、いずれかの緑カエルが残ればクリアです) 同じカエルが動き続ける限り1手として、最少手数で解きます。 Q1 緑 ○ ○ 緑 ○ ○ 緑 ○ 赤 ○ ○ ○ ○ Q2 緑 緑 ○ 緑 緑 緑 ○ ○ 赤 緑 ○ ○ ○ Q3 緑 緑 ○ 緑 ○ ○ 緑 緑 ○ 緑 ○ ○ 緑 Q4 (追加問題の1) ○ ○ 緑 緑 緑 緑 ○ 緑 緑 緑 緑 緑 ○ Q5 (追加問題の2) ○ ○ ○ 緑 緑 緑 ○ 緑 緑 緑 緑 緑 緑 Q6 (追加問題の3) ○ 緑 ○ 緑 緑 緑 緑 緑 緑 緑 緑 ○ 緑 Q7 (追加問題の4) ○ 緑 緑 緑 緑 緑 ○ ○ 緑 緑 緑 緑 緑