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[] {"人□羊羊□",
"□□□□□",
"□□□□羊",
"□羊□□□",
"□□□□□"};
}
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 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<long, int>();
MinTesuuDict.Add(GetHash(WillPush.BanArr), 0);
while (Stk.Count > 0) {
JyoutaiDef Popped = Stk.Pop();
//クリア判定
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;
for (int LoopX = 0; LoopX <= UB; LoopX++) {
for (int LoopY = 0; LoopY <= UB; LoopY++) {
if (Popped.BanArr[LoopX, LoopY] == '□') continue;
List<char[,]> MovedBanArrList =
DeriveMovedBanArrList(Popped.BanArr, LoopX, LoopY);
foreach (char[,] EachBanArr in MovedBanArrList) {
WillPush.Level = Popped.Level + 1;
WillPush.BanArr = EachBanArr;
long 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)
{
return pBanArr[2, 2] == '人';
}
//移動後の盤情報の配列を返す
static List<char[,]> DeriveMovedBanArrList(char[,] pBanArr, int pFromX, int pFromY)
{
var WillReturn = new List<char[,]>();
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> MoveAct = (pHeniX, pHeniY) =>
{
int CurrX = pFromX + pHeniX;
int CurrY = pFromY + pHeniY;
if (IsInside(CurrX, CurrY) == false) return;
if (pBanArr[CurrX, CurrY] == '人'
|| pBanArr[CurrX, CurrY] == '羊') return;
while (true) {
int NextX = CurrX + pHeniX;
int NextY = CurrY + pHeniY;
if (IsInside(NextX, NextY) == false) return;
//受け止めれる場合
if (pBanArr[NextX, NextY] == '人'
|| pBanArr[NextX, NextY] == '羊') {
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[pFromX, pFromY] = '□';
wkArr[CurrX, CurrY] = pBanArr[pFromX, pFromY];
WillReturn.Add(wkArr);
return;
}
CurrX = NextX;
CurrY = NextY;
}
};
MoveAct(0, -1);
MoveAct(0, +1);
MoveAct(+1, 0);
MoveAct(-1, 0);
return WillReturn;
}
//盤面をハッシュ値に変換
static long GetHash(char[,] pBanArr)
{
var NumList = new List<long>();
for (int X = 0; X <= UB; X++) {
for (int Y = 0; Y <= UB; Y++) {
if (pBanArr[X, Y] == '□') NumList.Add(0);
if (pBanArr[X, Y] == '人') NumList.Add(1);
if (pBanArr[X, Y] == '羊') NumList.Add(2);
}
}
//3の25乗=847288609443なので3進数ならオーバーフローしない
long WillReturn = 0;
foreach (long EachInt in NumList) {
WillReturn *= 3;
WillReturn += EachInt;
}
return WillReturn;
}
//盤面を出力
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());
}
}
人と山羊は、上下左右に移動できますが、停止するには、 人か山羊に、当たる必要があります。 また、山羊の盤外移動は不可です。 人が盤面中央のゴールで停止すればクリアです。 Q01 □羊□□人 □□□□□ □□□□□ □□羊□□ □□□□□ Q02 羊□□□羊 □□□羊□ □□□□□ □羊□□□ 羊□□□人 Q03 □□□□羊 □□羊□□ □羊□□□ □□□羊□ □□□□人 Q04 □□人□□ 羊□□□羊 羊□□□□ □□□□□ □羊□羊□ Q05 (追加問題の41) □羊人羊羊 □□□□□ □□□□□ □□□□□ □□羊□□ Q06 (追加問題の45) 人□羊羊□ □□□□□ □□□□羊 □羊□□□ □□□□□ Q07 (追加問題の49) □人□□□ □□□羊□ □□□□□ □□□□□ 羊□□羊羊 Q08 (追加問題の53) □人□□羊 羊□□□□ □□□□羊 □□□□□ □□羊□羊 Q09 (追加問題の54) □人□□□ □羊□□羊 □□□□□ □□□□□ □羊□□羊 Q10 (追加問題の55) 羊人□□□ □□□□羊 □□□□□ 羊□□□□ 羊□羊□□ Q11 (追加問題の56) 人□□羊□ □□□□□ □□□□羊 □□□□羊 羊□□□羊