using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
const int UB = 6;
static char[,] mQuestionArr; //問題の盤面
//問題を定義
static void QuestionDef()
{
string[] Q01Arr ={"□□□□□□□",
"□□□□熊□□",
"□□熊□□□□",
"□□□□□□□",
"□熊□□熊●●",
"□□□□□●□",
"□□□□□●●"};
string[] Q02Arr ={"□□□熊□□□",
"□□熊●●□□",
"□□□□●□□",
"□□□●●□□",
"□□□□熊□□",
"□熊□□□□□",
"□□□□□□□"};
string[] Q03Arr ={"□□□□□□□",
"□□熊●●●□",
"□□□●□●□",
"□□□熊□□□",
"□□□□熊□□",
"□□□熊□□□",
"□□□□□□□"};
string[] Q09Arr ={"□□□□□□□",
"□●●●□□熊",
"□●熊●□□□",
"□熊□□□□□",
"□□□熊□□□",
"□□□□□□□",
"□□□□□□□"};
string[] Q10Arr ={"□□□□□□□",
"□□□熊□□□",
"□□□□熊□□",
"□□□熊□□□",
"●●熊□□□□",
"●□□□□□□",
"●●□□□□□"};
string[] Q40Arr ={"□□熊□□□□",
"□□□□□□□",
"□□熊□□□□",
"●□●熊□□□",
"●●●□□□□",
"□□□□□□□",
"□□熊□□□□"};
string[] Q41Arr ={"□□●●●□□",
"□□●□●熊□",
"□□□□□□□",
"□□□熊□□□",
"□熊□□□□□",
"□熊□□□□□",
"□□□□□□□"};
string[] Q42Arr ={"熊□□□□□□",
"□□□□□□□",
"●●□□□□□",
"□●□熊□□□",
"●●熊□□□□",
"□□□□□□熊",
"□□□□□□□"};
string[] Q43Arr ={"熊□□□□□□",
"□□□□□□□",
"□□熊□□□□",
"□□□熊□□□",
"□□□□□□□",
"●●●□□□□",
"●□●熊□□□"};
string[] Q44Arr ={"□□□□□□□",
"□□□□□□□",
"□□□□熊□□",
"□□熊□□□□",
"□□□□熊□□",
"□□□□●□●",
"□熊□□●●●"};
mQuestionArr = XYRev(Q01Arr);
//mQuestionArr = XYRev(Q02Arr);
//mQuestionArr = XYRev(Q03Arr);
//mQuestionArr = XYRev(Q09Arr);
//mQuestionArr = XYRev(Q10Arr);
//mQuestionArr = XYRev(Q40Arr);
//mQuestionArr = XYRev(Q41Arr);
//mQuestionArr = XYRev(Q42Arr);
//mQuestionArr = XYRev(Q43Arr);
//mQuestionArr = XYRev(Q44Arr);
}
//String型を引数として、X座標とY座標の入れ替えたChar型の配列を返す
static char[,] XYRev(string[] pStrArr)
{
int RevArrUB_X = pStrArr[0].Length - 1;
int RevArrUB_Y = pStrArr.GetUpperBound(0);
char[,] WillReturnArr = new char[RevArrUB_X + 1, RevArrUB_Y + 1];
for (int X = 0; X <= RevArrUB_X; X++) {
for (int Y = 0; Y <= RevArrUB_Y; Y++) {
WillReturnArr[X, Y] = pStrArr[Y][X];
}
}
return WillReturnArr;
}
static void Main()
{
//状態の盤面定義
JyoutaiCharArrDef();
//状態ID間のリンクを定義
JyoutaiLinkDef();
//熊と接しているかの判定定義
KumaHanteiDef();
//問題を定義
QuestionDef();
//問題を読み込む
int CurrX, CurrY;
string CurrJyoutaiID;
LoadQuestion(out CurrX, out CurrY, out CurrJyoutaiID);
Solve(CurrX, CurrY, CurrJyoutaiID);
}
static Dictionary<string, char[,]>
mJyoutaiCharArrDict = new Dictionary<string, char[,]>();
//状態の盤面定義
static void JyoutaiCharArrDef()
{
//横2、縦3の状態
string[] Jyoutai01 ={"●●",
"●□",
"●●"};
string[] Jyoutai02 ={"●●",
"●●",
"●●"};
string[] Jyoutai03 ={"●●",
"□●",
"●●"};
string[] Jyoutai04 ={"●●",
"○○",
"●●"};
//横3、縦2の状態
string[] Jyoutai05 ={"●●●",
"●□●"};
string[] Jyoutai06 ={"●○●",
"●○●"};
string[] Jyoutai07 ={"●□●",
"●●●"};
string[] Jyoutai08 ={"●●●",
"●●●"};
//横2、縦2の状態
string[] Jyoutai09 ={"●●",
"○○"};
string[] Jyoutai10 ={"○●",
"○●"};
string[] Jyoutai11 ={"○○",
"●●"};
string[] Jyoutai12 ={"●○",
"●○"};
mJyoutaiCharArrDict.Add("01", XYRev(Jyoutai01));
mJyoutaiCharArrDict.Add("02", XYRev(Jyoutai02));
mJyoutaiCharArrDict.Add("03", XYRev(Jyoutai03));
mJyoutaiCharArrDict.Add("04", XYRev(Jyoutai04));
mJyoutaiCharArrDict.Add("05", XYRev(Jyoutai05));
mJyoutaiCharArrDict.Add("06", XYRev(Jyoutai06));
mJyoutaiCharArrDict.Add("07", XYRev(Jyoutai07));
mJyoutaiCharArrDict.Add("08", XYRev(Jyoutai08));
mJyoutaiCharArrDict.Add("09", XYRev(Jyoutai09));
mJyoutaiCharArrDict.Add("10", XYRev(Jyoutai10));
mJyoutaiCharArrDict.Add("11", XYRev(Jyoutai11));
mJyoutaiCharArrDict.Add("12", XYRev(Jyoutai12));
}
struct LinkDef
{
internal string FromID;
internal string ToID;
internal int Heni_X;
internal int Heni_Y;
}
static LinkDef[] mLinkArr;
//状態ID間のリンクを定義
static void JyoutaiLinkDef()
{
var LinkList = new List<LinkDef>();
Action<string, string, int, int> AddAct = (pFromID, pToID, pHeni_X, pHeni_Y) =>
{
LinkDef WillAdd;
WillAdd.FromID = pFromID;
WillAdd.ToID = pToID;
WillAdd.Heni_X = pHeni_X;
WillAdd.Heni_Y = pHeni_Y;
LinkList.Add(WillAdd);
};
//●●
//●□
//●●
AddAct("01", "12", 0, -1); //上方向に移動
AddAct("01", "02", 1, 0); //右方向に移動
AddAct("01", "12", 0, 2); //下方向に移動
AddAct("01", "04", -1, 0); //左方向に移動
//●●
//●●
//●●
AddAct("02", "09", 0, -1); //上方向に移動
AddAct("02", "03", 1, 0); //右方向に移動
AddAct("02", "11", 0, 2); //下方向に移動
AddAct("02", "01", -1, 0); //左方向に移動
//●●
//□●
//●●
AddAct("03", "10", 0, -1); //上方向に移動
AddAct("03", "04", 1, 0); //右方向に移動
AddAct("03", "10", 0, 2); //下方向に移動
AddAct("03", "02", -1, 0); //左方向に移動
//●●
//○○
//●●
AddAct("04", "11", 0, -1); //上方向に移動
AddAct("04", "01", 1, 0); //右方向に移動
AddAct("04", "09", 0, 2); //下方向に移動
AddAct("04", "03", -1, 0); //左方向に移動
//●●●
//●□●
AddAct("05", "06", 0, -1); //上方向に移動
AddAct("05", "09", 2, 0); //右方向に移動
AddAct("05", "08", 0, 1); //下方向に移動
AddAct("05", "09", -1, 0); //左方向に移動
//●○●
//●○●
AddAct("06", "07", 0, -1); //上方向に移動
AddAct("06", "12", 2, 0); //右方向に移動
AddAct("06", "05", 0, 1); //下方向に移動
AddAct("06", "10", -1, 0); //左方向に移動
//●□●
//●●●
AddAct("07", "08", 0, -1); //上方向に移動
AddAct("07", "11", 2, 0); //右方向に移動
AddAct("07", "06", 0, 1); //下方向に移動
AddAct("07", "11", -1, 0); //左方向に移動
//●●●
//●●●
AddAct("08", "05", 0, -1); //上方向に移動
AddAct("08", "10", 2, 0); //右方向に移動
AddAct("08", "07", 0, 1); //下方向に移動
AddAct("08", "12", -1, 0); //左方向に移動
//●●
//○○
AddAct("09", "04", 0, -2); //上方向に移動
AddAct("09", "05", 1, 0); //右方向に移動
AddAct("09", "02", 0, 1); //下方向に移動
AddAct("09", "05", -2, 0); //左方向に移動
//○●
//○●
AddAct("10", "03", 0, -2); //上方向に移動
AddAct("10", "06", 1, 0); //右方向に移動
AddAct("10", "03", 0, 1); //下方向に移動
AddAct("10", "08", -2, 0); //左方向に移動
//○○
//●●
AddAct("11", "02", 0, -2); //上方向に移動
AddAct("11", "07", 1, 0); //右方向に移動
AddAct("11", "04", 0, 1); //下方向に移動
AddAct("11", "07", -2, 0); //左方向に移動
//●○
//●○
AddAct("12", "01", 0, -2); //上方向に移動
AddAct("12", "08", 1, 0); //右方向に移動
AddAct("12", "01", 0, 1); //下方向に移動
AddAct("12", "06", -2, 0); //左方向に移動
mLinkArr = LinkList.ToArray();
}
//熊と接しているかの判定
struct KumaHanteiInfoDef
{
internal string JyoutaiID;
internal int HeniX;
internal int HeniY;
}
static List<KumaHanteiInfoDef> mKumaHanteiInfoList = new List<KumaHanteiInfoDef>();
//熊と接しているかの判定定義
static void KumaHanteiDef()
{
Action<string, int, int> AddAct = (pJyoutaiID, pHeniX, pHeniY) =>
{
KumaHanteiInfoDef WillAdd;
WillAdd.JyoutaiID = pJyoutaiID;
WillAdd.HeniX = pHeniX;
WillAdd.HeniY = pHeniY;
mKumaHanteiInfoList.Add(WillAdd);
};
//●●
//●□
//●●
AddAct("01", 0, 0); AddAct("01", 1, 0);
AddAct("01", 0, 1);
AddAct("01", 0, 2); AddAct("01", 1, 2);
//●●
//●●
//●●
AddAct("02", 0, 0); AddAct("02", 1, 0);
AddAct("02", 0, 2); AddAct("02", 1, 2);
//●●
//□●
//●●
AddAct("03", 0, 0); AddAct("03", 1, 0);
AddAct("03", 1, 1);
AddAct("03", 0, 2); AddAct("03", 1, 2);
//●●
//○○
//●●
AddAct("04", 0, 0); AddAct("04", 1, 0);
AddAct("04", 0, 1); AddAct("04", 1, 1);
AddAct("04", 0, 2); AddAct("04", 1, 2);
//●●●
//●□●
AddAct("05", 0, 0); AddAct("05", 1, 0); AddAct("05", 2, 0);
AddAct("05", 0, 1); AddAct("05", 2, 1);
//●○●
//●○●
AddAct("06", 0, 0); AddAct("06", 1, 0); AddAct("06", 2, 0);
AddAct("06", 0, 1); AddAct("06", 1, 1); AddAct("06", 2, 1);
//●□●
//●●●
AddAct("07", 0, 0); AddAct("07", 2, 0);
AddAct("07", 0, 1); AddAct("07", 1, 1); AddAct("07", 2, 1);
//●●●
//●●●
AddAct("08", 0, 0); AddAct("08", 2, 0);
AddAct("08", 0, 1); AddAct("08", 2, 1);
//●●
//○○
AddAct("09", 0, 0); AddAct("09", 1, 0);
AddAct("09", 0, 1); AddAct("09", 1, 1);
//○●
//○●
AddAct("10", 0, 0); AddAct("10", 1, 0);
AddAct("10", 0, 1); AddAct("10", 1, 1);
//○○
//●●
AddAct("11", 0, 0); AddAct("11", 1, 0);
AddAct("11", 0, 1); AddAct("11", 1, 1);
//●○
//●○
AddAct("12", 0, 0); AddAct("12", 1, 0);
AddAct("12", 0, 1); AddAct("12", 1, 1);
}
//問題を読み込む
static void LoadQuestion(out int pCurrX, out int pCurrY, out string pCurrJyoutaiID)
{
int BaseX = -1, BaseY = -1;
bool WillBreak = false;
for (int LoopX = 0; LoopX <= UB; LoopX++) {
for (int LoopY = 0; LoopY <= UB; LoopY++) {
if (mQuestionArr[LoopX, LoopY] == '●'
|| mQuestionArr[LoopX, LoopY] == '○') {
BaseX = LoopX; BaseY = LoopY;
WillBreak = true;
break;
}
}
if (WillBreak) break;
}
pCurrX = BaseX;
pCurrY = BaseY;
pCurrJyoutaiID = "";
foreach (var EachPair in mJyoutaiCharArrDict) {
char[,] EachCharArr = EachPair.Value;
bool IsOK = true;
for (int LoopX = 0; LoopX <= EachCharArr.GetUpperBound(0); LoopX++) {
for (int LoopY = 0; LoopY <= EachCharArr.GetUpperBound(1); LoopY++) {
if (UB < BaseX + LoopX) {
IsOK = false;
break;
}
if (UB < BaseY + LoopY) {
IsOK = false;
break;
}
char wk1 = EachCharArr[LoopX, LoopY];
char wk2 = mQuestionArr[BaseX + LoopX, BaseY + LoopY];
if (wk1 == '□' && wk2 == '熊') continue;
if (wk1 != wk2) {
IsOK = false;
break;
}
}
if (IsOK == false) break;
}
if (IsOK) pCurrJyoutaiID = EachPair.Key;
}
//問題図からハリネズミを消去
for (int LoopX = 0; LoopX <= UB; LoopX++) {
for (int LoopY = 0; LoopY <= UB; LoopY++) {
if (mQuestionArr[LoopX, LoopY] == '●'
|| mQuestionArr[LoopX, LoopY] == '○') {
mQuestionArr[LoopX, LoopY] = '□';
}
}
}
}
struct JyoutaiDef
{
internal int Level;
internal string CurrJyoutaiID;
internal int CurrX;
internal int CurrY;
internal List<string> Log;
}
static void Solve(int pCurrX, int pCurrY, string pCurrJyoutaiID)
{
var Que = new Queue<JyoutaiDef>();
JyoutaiDef WillEnqueue;
WillEnqueue.Level = 0;
WillEnqueue.CurrJyoutaiID = pCurrJyoutaiID;
WillEnqueue.CurrX = pCurrX;
WillEnqueue.CurrY = pCurrY;
WillEnqueue.Log = new List<string>();
WillEnqueue.Log.Add(DeriveBanStr(WillEnqueue));
Que.Enqueue(WillEnqueue);
var VisitedSet = new HashSet<int>();
VisitedSet.Add(GetHash(WillEnqueue));
while (Que.Count > 0) {
JyoutaiDef Dequeued = Que.Dequeue();
//クリア判定
if (IsClear(Dequeued)) {
Console.WriteLine("{0}手の解を発見", Dequeued.Level);
for (int I = 0; I <= Dequeued.Log.Count - 1; I++) {
Console.WriteLine("{0}手目", I);
Console.WriteLine(Dequeued.Log[I]);
}
break;
}
//状態遷移を行う
foreach (LinkDef EachLink in mLinkArr) {
if (EachLink.FromID != Dequeued.CurrJyoutaiID) continue;
WillEnqueue.Level = Dequeued.Level + 1;
WillEnqueue.CurrJyoutaiID = EachLink.ToID;
//範囲外かの判定
int Haba_X = mJyoutaiCharArrDict[EachLink.ToID].GetUpperBound(0);
int Haba_Y = mJyoutaiCharArrDict[EachLink.ToID].GetUpperBound(1);
int NewX = Dequeued.CurrX + EachLink.Heni_X;
int NewY = Dequeued.CurrY + EachLink.Heni_Y;
if (NewX < 0 || UB < NewX + Haba_X) continue;
if (NewY < 0 || UB < NewY + Haba_Y) continue;
WillEnqueue.CurrX = NewX;
WillEnqueue.CurrY = NewY;
//熊に接する場合はNG
bool IsOK = true;
foreach (KumaHanteiInfoDef EachKumaHanteiInfo in mKumaHanteiInfoList) {
if (EachKumaHanteiInfo.JyoutaiID != WillEnqueue.CurrJyoutaiID)
continue;
int TargetX = WillEnqueue.CurrX + EachKumaHanteiInfo.HeniX;
int TargetY = WillEnqueue.CurrY + EachKumaHanteiInfo.HeniY;
if (mQuestionArr[TargetX, TargetY] == '熊') {
IsOK = false;
break;
}
}
if (IsOK == false) continue;
//再訪防止
if (VisitedSet.Add(GetHash(WillEnqueue)) == false)
continue;
WillEnqueue.Log = new List<string>(Dequeued.Log);
WillEnqueue.Log.Add(DeriveBanStr(WillEnqueue));
Que.Enqueue(WillEnqueue);
}
}
}
//クリア判定
static bool IsClear(JyoutaiDef pJyoutai)
{
if (pJyoutai.CurrX != 5) return false;
if (pJyoutai.CurrY != 3) return false;
return pJyoutai.CurrJyoutaiID == "12";
}
//ハッシュ値を求める
static int GetHash(JyoutaiDef pJyoutai)
{
int WillReturn = 0;
WillReturn += pJyoutai.CurrX * 1000;
WillReturn += pJyoutai.CurrY * 100;
WillReturn += int.Parse(pJyoutai.CurrJyoutaiID);
return WillReturn;
}
//盤面にハリネズミを描画したString型を返す
static string DeriveBanStr(JyoutaiDef pJyoutai)
{
char[,] JyoutaiCharArr = mJyoutaiCharArrDict[pJyoutai.CurrJyoutaiID];
int UB_X = JyoutaiCharArr.GetUpperBound(0);
int UB_Y = JyoutaiCharArr.GetUpperBound(1);
char[,] wkArr = (char[,])mQuestionArr.Clone();
for (int X = 0; X <= UB_X; X++) {
for (int Y = 0; Y <= UB_Y; Y++) {
char wkChar1 = JyoutaiCharArr[X, Y];
char wkChar2 = wkArr[pJyoutai.CurrX + X, pJyoutai.CurrY + Y];
if (wkChar1 == '□' && wkChar2 == '熊')
wkArr[pJyoutai.CurrX + X, pJyoutai.CurrY + Y] = '熊';
else
wkArr[pJyoutai.CurrX + X, pJyoutai.CurrY + Y] = wkChar1;
}
}
return BanToStr(wkArr);
}
//盤面をString型で表現
static string BanToStr(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();
}
return sb.ToString();
}
}
Q01 □□□□□□□ □□□□熊□□ □□熊□□□□ □□□□□□□熊□□ □熊□□熊●●熊□□ □□□□□●□ □□□□□●● Q02 □□□熊□□□ □□熊●●□□ □□□□●□□ □□□●●□□熊□□ □□□□熊□□熊□□ □熊□□□□□ □□□□□□□ Q03 □□□□□□□ □□熊●●●□ □□□●□●□ □□□熊□□□熊□□ □□□□熊□□熊□□ □□□熊□□□ □□□□□□□ Q09 □□□□□□□ □●●●□□熊 □●熊●□□□ □熊□□□□□熊□□ □□□熊□□□熊□□ □□□□□□□ □□□□□□□ Q10 □□□□□□□ □□□熊□□□ □□□□熊□□ □□□熊□□□熊□□ ●●熊□□□□熊□□ ●□□□□□□ ●●□□□□□ Q40 □□熊□□□□ □□□□□□□ □□熊□□□□ ●□●熊□□□熊□□ ●●●□□□□熊□□ □□□□□□□ □□熊□□□□ Q41 □□●●●□□ □□●□●熊□ □□□□□□□ □□□熊□□□熊□□ □熊□□□□□熊□□ □熊□□□□□ □□□□□□□ Q42 熊□□□□□□ □□□□□□□ ●●□□□□□ □●□熊□□□熊□□ ●●熊□□□□熊□□ □□□□□□熊 □□□□□□□ Q43 熊□□□□□□ □□□□□□□ □□熊□□□□ □□□熊□□□熊□□ □□□□□□□熊□□ ●●●□□□□ ●□●熊□□□ Q44 □□□□□□□ □□□□□□□ □□□□熊□□ □□熊□□□□熊□□ □□□□熊□□熊□□ □□□□●□● □熊□□●●●