using System;
using System.Collections.Generic;
class Program
{
static int mQuestionNo = 2;
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[] {"●１□２●",
"□１□２Ｍ",
"Ｍ□●□Ｍ",
"Ｒ□□□□",
"●□□□●"};
}
if (mQuestionNo == 8) {
wkStrArr = new string[] {"●□□□●",
"□□１１□",
"Ｍ□●Ｍ□",
"２２□□□",
"Ｍ□□Ｒ●"};
}
if (mQuestionNo == 9) {
wkStrArr = new string[] {"●１□Ｒ●",
"□１□Ｍ□",
"□□●□Ｒ",
"□□□２２",
"●ＲＭ□●"};
}
if (mQuestionNo == 10) {
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 List<char[,]> Log;
}
static void Main()
{
//問題を定義
QuestionDef();
//幅優先探索で解く
var Que = new Queue<JyoutaiDef>();
JyoutaiDef WillEnqueue;
WillEnqueue.Level = 0;
WillEnqueue.BanArr = mQuestionArr;
WillEnqueue.Log = new List<char[,]>() { WillEnqueue.BanArr };
Que.Enqueue(WillEnqueue);
//訪問済の盤面
var VisitedSet = new HashSet<string>();
VisitedSet.Add(GetHash(WillEnqueue.BanArr));
while (Que.Count > 0) {
JyoutaiDef Dequeued = Que.Dequeue();
//クリア判定
if (IsClear(Dequeued.BanArr)) {
Console.WriteLine("解を発見");
for (int I = 0; I <= Dequeued.Log.Count - 1; I++) {
Console.WriteLine("レベル{0}", I);
PrintBan(Dequeued.Log[I]);
}
return;
}
for (int LoopX = 0; LoopX <= UB; LoopX++) {
for (int LoopY = 0; LoopY <= UB; LoopY++) {
// 移動後の盤面のList
var MoveList = new List<char[,]>();
//ウサギの座標の場合
if (Dequeued.BanArr[LoopX, LoopY] == 'Ｒ') {
MoveList = DeriveUsagiMoveList(Dequeued.BanArr, LoopX, LoopY);
}
//キツネの左上座標の場合
int FoxHeniX, FoxHeniY;
if (GetFoxInfo(Dequeued.BanArr, LoopX, LoopY, out FoxHeniX, out FoxHeniY)) {
MoveList = DeriveFoxMoveList(Dequeued.BanArr, LoopX, LoopY, FoxHeniX, FoxHeniY);
}
foreach (char[,] EachMove in MoveList) {
WillEnqueue.Level = Dequeued.Level + 1;
WillEnqueue.BanArr = EachMove;
WillEnqueue.Log = new List<char[,]>(Dequeued.Log) { WillEnqueue.BanArr };
string CurrHash = GetHash(WillEnqueue.BanArr);
if (VisitedSet.Add(CurrHash)) {
Que.Enqueue(WillEnqueue);
}
}
}
}
}
}
//クリア判定
static bool IsClear(char[,] pBanArr)
{
for (int Y = 0; Y <= UB; Y++) {
for (int X = 0; X <= UB; X++) {
if (pBanArr[X, Y] != 'Ｒ') continue;
if (IsHole(X, Y) == false) return false;
}
}
return true;
}
//穴が存在する座標かを返す
static bool IsHole(int pX, int pY)
{
if (pX == 0 && pY == 0) return true;
if (pX == 0 && pY == UB) return true;
if (pX == UB && pY == 0) return true;
if (pX == UB && pY == UB) return true;
if (pX == UB / 2 && pY == UB / 2) return true;
return false;
}
//座標を引数として、移動後のマスを返す
static char DeriveMovedMasu(int pX, int pY)
{
if (IsHole(pX, pY)) return '●';
return '□';
}
//盤面の内部かを返す
static bool IsInside(int pX, int pY)
{
if (pX < 0 || UB < pX) return false;
if (pY < 0 || UB < pY) return false;
return true;
}
//ウサギがジャンプ後の盤情報の配列を返す
static List<char[,]> DeriveUsagiMoveList(char[,] pBanArr, int pFromX, int pFromY)
{
var WillReturn = new List<char[,]>();
Action<int, int, int> MoveAct = (pHeniX, pHeniY, pAbs) =>
{
int GoalX = pFromX + pHeniX * pAbs;
int GoalY = pFromY + pHeniY * pAbs;
if (IsInside(GoalX, GoalY) == false) return;
if (pBanArr[GoalX, GoalY] != '●' &&
pBanArr[GoalX, GoalY] != '□') return;
//移動先までの間に、ウサギ、キノコ、キツネのいずれかがあること
for (int LoopAbs = 1; LoopAbs <= pAbs - 1; LoopAbs++) {
int CheckX = pFromX + pHeniX * LoopAbs;
int CheckY = pFromY + pHeniY * LoopAbs;
bool IsOK = false;
if (pBanArr[CheckX, CheckY] == 'Ｒ') IsOK = true;
if (pBanArr[CheckX, CheckY] == 'Ｍ') IsOK = true;
if (pBanArr[CheckX, CheckY] == '１') IsOK = true;
if (pBanArr[CheckX, CheckY] == '２') IsOK = true;
if (IsOK == false) return;
}
//移動元を変更
char[,] WillAdd = (char[,])pBanArr.Clone();
WillAdd[pFromX, pFromY] = DeriveMovedMasu(pFromX, pFromY);
//移動先を変更
WillAdd[GoalX, GoalY] = 'Ｒ';
WillReturn.Add(WillAdd);
};
//移動先のループ
for (int I = 2; I <= UB; I++) {
MoveAct(0, -1, I);
MoveAct(0, +1, I);
MoveAct(+1, 0, I);
MoveAct(-1, 0, I);
}
return WillReturn;
}
//キツネの左上座標かを返す
static bool GetFoxInfo(char[,] pBanArr, int pCurrX, int pCurrY, out int pFoxHeniX, out int pFoxHeniY)
{
pFoxHeniX = pFoxHeniY = 0;
char CurrMasu = pBanArr[pCurrX, pCurrY];
if (CurrMasu != '１' && CurrMasu != '２') return false;
//下に連結している場合
if (IsInside(pCurrX, pCurrY + 1)) {
if (pBanArr[pCurrX, pCurrY + 1] == CurrMasu) {
pFoxHeniX = 0; pFoxHeniY = 1;
return true;
}
}
//右に連結している場合
if (IsInside(pCurrX + 1, pCurrY)) {
if (pBanArr[pCurrX + 1, pCurrY] == CurrMasu) {
pFoxHeniX = 1; pFoxHeniY = 0;
return true;
}
}
//キツネの座標だが、左上の座標でない場合
return false;
}
//キツネが移動後の盤情報の配列を返す
static List<char[,]> DeriveFoxMoveList(char[,] pBanArr, int pFromX, int pFromY,
int pFoxHeniX, int pFoxHeniY)
{
var WillReturn = new List<char[,]>();
char CurrMasu = pBanArr[pFromX, pFromY];
//移動前のキツネの座標のList
var BeforeFoxPosList = new List<PointDef>();
BeforeFoxPosList.Add(new PointDef() { X = pFromX, Y = pFromY });
BeforeFoxPosList.Add(new PointDef() { X = pFromX + pFoxHeniX, Y = pFromY + pFoxHeniY });
foreach (int EachAbs in (new int[] { -1, 1 })) {
bool CanMove = true;
//移動後のキツネの座標のList
var AfterFoxPosList = new List<PointDef>();
foreach (PointDef EachFoxPos in BeforeFoxPosList) {
int TargetX = EachFoxPos.X + pFoxHeniX * EachAbs;
int TargetY = EachFoxPos.Y + pFoxHeniY * EachAbs;
if (IsInside(TargetX, TargetY) == false) {
CanMove = false;
break;
}
if (pBanArr[TargetX, TargetY] == '□'
|| pBanArr[TargetX, TargetY] == CurrMasu) {
AfterFoxPosList.Add(new PointDef() { X = TargetX, Y = TargetY });
}
else CanMove = false;
}
if (CanMove) {
char[,] WillAdd = (char[,])pBanArr.Clone();
BeforeFoxPosList.ForEach(pEach => WillAdd[pEach.X, pEach.Y] = '□');
AfterFoxPosList.ForEach(pEach => WillAdd[pEach.X, pEach.Y] = CurrMasu);
WillReturn.Add(WillAdd);
}
}
return WillReturn;
}
//盤面をハッシュ値に変換
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++) {
sb.Append(pBanArr[X, 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つ以上跳び越す移動ができます。 全てのウサギが●に移動できればクリアです。 Q01 ●Ｒ□Ｍ● □□Ｍ□□ □□●□□ □□Ｍ□□ ●□Ｒ□● Q02 ●□□Ｆ● Ｍ□□Ｆ□ □Ｍ●□Ｒ □□Ｍ□□ ●□Ｒ□● Q03 (13問目) ●□□Ｍ● □ＭＲＦＦ □□Ｍ□□ □□□□□ ●□□□● Q04 (14問目) ●□□Ｒ● □ＦＦ□□ □ＭＭ□Ｍ □□□□□ ●□□□● Q05 (15問目) ●□ＭＦ● □□□Ｆ□ □□Ｍ□□ □□Ｍ□Ｒ ●□□□● Q06 (16問目) ●Ｒ□□● Ｍ□□□□ Ｍ□●□□ □ＦＭ□□ ●Ｆ□□● Q07 (17問目) ●Ｆ□Ｆ● □Ｆ□ＦＭ Ｍ□●□Ｍ Ｒ□□□□ ●□□□● Q08 (18問目) ●□□□● □□ＦＦ□ Ｍ□●Ｍ□ ＦＦ□□□ Ｍ□□Ｒ● Q09 (20問目) ●Ｆ□Ｒ● □Ｆ□Ｍ□ □□●□Ｒ □□□ＦＦ ●ＲＭ□● Q10 ●□□□Ｍ ＦＦ□Ｒ□ □Ｆ●□Ｒ □ＦＭ□□ Ｍ□□Ｒ●