using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
const int UB = 6;
static int mQuestionNo = 1;
static char[,] mQuestionArr = new char[UB + 1, UB + 1]; //問題の初期盤面
static char mCar; //車の文字
static char[] mPieceArr;
struct PointDef
{
internal int X;
internal int Y;
}
//問題を定義
static void QuestionDef()
{
string[] wkStrArr = null;
if (mQuestionNo == 1) {
wkStrArr = new string[] {"□□□□□□□",
"□ＡＡＡＢ□□",
"ＣＣ□□ＢＤ□",
"Ｅ□ＦＦ□Ｄ□",
"Ｅ□ＦＦ□Ｄ□",
"ＥＧ□□ＨＨ□",
"□ＧＩＩＩ□□"};
mCar = 'Ｆ';
}
if (mQuestionNo == 2) {
wkStrArr = new string[] {"ＡＡＡ□ＢＢ□",
"□ＣＣ□Ｄ□Ｅ",
"□ＣＣ□Ｄ□Ｅ",
"□ＦＦＦＤ□Ｇ",
"□□□ＨＩＩＧ",
"Ｊ□□ＨＩＩ□",
"Ｊ□ＫＫＬＬＬ"};
mCar = 'Ｃ';
}
if (mQuestionNo == 3) {
wkStrArr = new string[] {"□□□ＡＢ□□",
"□□ＣＡＢＤ□",
"□ＥＣＦＢＤＧ",
"ＨＥＣＦＩＩＧ",
"Ｈ□ＪＪＩＩＫ",
"Ｌ□ＪＪＭＭＫ",
"Ｌ□ＮＮＭＭＫ"};
mCar = 'Ｉ';
}
if (mQuestionNo == 4) {
wkStrArr = new string[] {"□□□□□□□",
"□□□□ＡＡＡ",
"ＢＢＢＣＤ□□",
"□□□ＣＤＥＥ",
"□ＦＦＣＤ□□",
"□□□ＧＧ□□",
"□□□ＧＧ□□"};
mCar = 'Ｇ';
}
for (int X = 0; X <= UB; X++) {
for (int Y = 0; Y <= UB; Y++) {
mQuestionArr[X, Y] = wkStrArr[Y][X];
}
}
mPieceArr = mQuestionArr.Cast<char>().Where(A => A != '□').Distinct().ToArray();
Array.Sort<char>(mPieceArr);
}
struct JyoutaiDef
{
internal char[,] BanArr;
internal int Level;
internal List<string> Log;
}
static void Main()
{
var sw = System.Diagnostics.Stopwatch.StartNew();
//問題を定義
QuestionDef();
//ピースの配置情報を取得
DerivePieceHeniListDict();
var Que = new Queue<JyoutaiDef>();
JyoutaiDef WillEnqueue;
WillEnqueue.BanArr = mQuestionArr;
WillEnqueue.Level = 0;
WillEnqueue.Log = new List<string>();
WillEnqueue.Log.Add(BanToStr(WillEnqueue.BanArr));
Que.Enqueue(WillEnqueue);
var VisitedSet = new HashSet<decimal>();
VisitedSet.Add(GetHash(WillEnqueue.BanArr));
while (Que.Count > 0) {
JyoutaiDef Dequeued = Que.Dequeue();
if (IsClear(Dequeued.BanArr)) {
Console.WriteLine("{0}手の解を発見。経過時間={1}", Dequeued.Level, sw.Elapsed);
for (int I = 0; I <= Dequeued.Log.Count - 1; I++) {
Console.WriteLine("{0}手目", I);
Console.WriteLine(Dequeued.Log[I]);
}
break;
}
foreach (char EachPiece in mPieceArr) {
//盤面とピースを引数として、1手後の盤面のListを返す
List<char[,]> MovedBanArrList = DeriveMovedBanArrList(Dequeued.BanArr, EachPiece);
foreach (char[,] EachMovedArr in MovedBanArrList) {
WillEnqueue.BanArr = EachMovedArr;
//再訪防止
if (VisitedSet.Add(GetHash(WillEnqueue.BanArr)) == false)
continue;
WillEnqueue.Level = Dequeued.Level + 1;
WillEnqueue.Log = new List<string>(Dequeued.Log);
WillEnqueue.Log.Add(BanToStr(WillEnqueue.BanArr));
Que.Enqueue(WillEnqueue);
}
}
}
}
//ピースの配置情報を取得
static Dictionary<char, List<PointDef>> mPieceHeniListDict = new Dictionary<char, List<PointDef>>();
static void DerivePieceHeniListDict()
{
foreach (char EachPiece in mPieceArr) {
bool FirstFlag = true;
PointDef GentenPos = new PointDef() { X = -1, Y = -1 };
for (int LoopY = 0; LoopY <= UB; LoopY++) {
for (int LoopX = 0; LoopX <= UB; LoopX++) {
if (mQuestionArr[LoopX, LoopY] != EachPiece) continue;
if (FirstFlag) {
FirstFlag = false;
GentenPos.X = LoopX;
GentenPos.Y = LoopY;
mPieceHeniListDict.Add(EachPiece, new List<PointDef>());
}
//原点 + 変位ベクトル = カレント座標
//を移項
PointDef HeniVect;
HeniVect.X = LoopX - GentenPos.X;
HeniVect.Y = LoopY - GentenPos.Y;
mPieceHeniListDict[EachPiece].Add(HeniVect);
}
}
}
}
//クリア判定
static bool IsClear(char[,] pBanArr)
{
return pBanArr[5, 2] == mCar && pBanArr[6, 2] == mCar
&& pBanArr[5, 3] == mCar && pBanArr[6, 3] == mCar;
}
//盤面とピースを引数として、1手後の盤面のListを返す
static List<char[,]> DeriveMovedBanArrList(char[,] pBanArr, char pPiece)
{
//ピースが、動物の場合
if (IsAnimal(pPiece))
return DeriveMovedBanArrListAnimal(pBanArr, pPiece);
//ピースが、車か巣の場合
return DeriveMovedBanArrListCar(pBanArr, pPiece);
}
//ピースが動物かを返す
static bool IsAnimal(char pPiece)
{
return mPieceHeniListDict[pPiece].Count < 4;
}
//盤面とピース(動物)を引数として、1手後の盤面のListを返す
static List<char[,]> DeriveMovedBanArrListAnimal(char[,] pBanArr, char pAnimal)
{
var WillReturn = new List<char[,]>();
MoveInfoDef wkMoveInfo = DeriveMoveInfo(pAnimal, pBanArr);
foreach (PointDef EachHeni in wkMoveInfo.HeniArr) {
char[,] wkArr = (char[,])pBanArr.Clone();
//移動後の両端の座標を求める
int MovedFromX = wkMoveInfo.FromPos.X + EachHeni.X;
int MovedFromY = wkMoveInfo.FromPos.Y + EachHeni.Y;
int MovedToX = wkMoveInfo.ToPos.X + EachHeni.X;
int MovedToY = wkMoveInfo.ToPos.Y + EachHeni.Y;
//空白に変更するループ
int StaX = Math.Min(MovedFromX, wkMoveInfo.FromPos.X);
int StaY = Math.Min(MovedFromY, wkMoveInfo.FromPos.Y);
int EndX = Math.Max(MovedToX, wkMoveInfo.ToPos.X);
int EndY = Math.Max(MovedToY, wkMoveInfo.ToPos.Y);
for (int X = StaX; X <= EndX; X++) {
for (int Y = StaY; Y <= EndY; Y++) {
wkArr[X, Y] = '□';
}
}
//ピースIDに変更するループ
for (int X = MovedFromX; X <= MovedToX; X++) {
for (int Y = MovedFromY; Y <= MovedToY; Y++) {
wkArr[X, Y] = pAnimal;
}
}
WillReturn.Add(wkArr);
}
return WillReturn;
}
//動物の移動情報
struct MoveInfoDef
{
internal PointDef FromPos; //両端の開始座標
internal PointDef ToPos; //両端の終了座標
internal PointDef[] HeniArr; //移動変位の配列
}
//動物のIDを引数として、動物の移動情報を返す
static MoveInfoDef DeriveMoveInfo(char pAnimal, char[,] pBanArr)
{
MoveInfoDef MoveInfo = new MoveInfoDef();
bool CanMoveYoko = DeriveCanMoveYoko(pAnimal);
bool WillBreak = false;
for (int LoopX = 0; LoopX <= UB; LoopX++) {
for (int LoopY = 0; LoopY <= UB; LoopY++) {
if (pBanArr[LoopX, LoopY] != pAnimal) continue;
MoveInfo.FromPos = new PointDef() { X = LoopX, Y = LoopY };
int AnimalLength = DeriveAnimalLength(pAnimal);
if (CanMoveYoko)
MoveInfo.ToPos = new PointDef() { X = LoopX + AnimalLength - 1, Y = LoopY };
else MoveInfo.ToPos = new PointDef() { X = LoopX, Y = LoopY + AnimalLength - 1 };
WillBreak = true;
break;
}
if (WillBreak) break;
}
var HeniList = new List<PointDef>();
Func<int, int, bool> AddFunc = (pI, pBasePos) =>
{
if (pBasePos + pI > UB) return false;
if (pBasePos + pI < 0) return false;
if (CanMoveYoko) {
if (pBanArr[pBasePos + pI, MoveInfo.FromPos.Y] != '□') return false;
HeniList.Add(new PointDef() { X = pI, Y = 0 });
}
else {
if (pBanArr[MoveInfo.FromPos.X, pBasePos + pI] != '□') return false;
HeniList.Add(new PointDef() { X = 0, Y = pI });
}
return true;
};
//変位が正の場合
for (int I = 1; I <= UB; I++) {
if (AddFunc(I, CanMoveYoko ? MoveInfo.ToPos.X : MoveInfo.ToPos.Y) == false)
break;
}
//変位が負の場合
for (int I = -1; I >= -UB; I--) {
if (AddFunc(I, CanMoveYoko ? MoveInfo.FromPos.X : MoveInfo.FromPos.Y) == false)
break;
}
MoveInfo.HeniArr = HeniList.ToArray();
return MoveInfo;
}
//動物が横に移動可かを返す
static bool DeriveCanMoveYoko(char pAnimal)
{
return mPieceHeniListDict[pAnimal][0].X != mPieceHeniListDict[pAnimal][1].X;
}
//動物の長さを返す
static int DeriveAnimalLength(char pAnimal)
{
return mPieceHeniListDict[pAnimal].Count;
}
//盤面とピース(車か巣)を引数として、1手後の盤面のListを返す
static List<char[,]> DeriveMovedBanArrListCar(char[,] pBanArr, char pPiece)
{
var WillReturn = new List<char[,]>();
var Stk = new Stack<char[,]>();
Stk.Push(pBanArr);
var VisitedSet = new HashSet<decimal>();
while (Stk.Count > 0) {
char[,] Popped = Stk.Pop();
List<char[,]> MovedBanArrList = DeriveMovedBanArrListCarHelper(Popped, pPiece);
foreach (char[,] EachBanArr in MovedBanArrList) {
decimal CurrHash = GetHash(EachBanArr);
if (CurrHash == GetHash(pBanArr)) continue;
if (VisitedSet.Add(CurrHash) == false) continue;
WillReturn.Add(EachBanArr);
Stk.Push(EachBanArr);
}
}
return WillReturn;
}
//盤面とピース(車か巣)を引数として、1手後の盤面のListを返す
static List<char[,]> DeriveMovedBanArrListCarHelper(char[,] pBanArr, char pPiece)
{
var WillReturn = new List<char[,]>();
PointDef wkPiecePoint = DerivePiecePoint(pBanArr, pPiece);
int CurrX = wkPiecePoint.X;
int CurrY = wkPiecePoint.Y;
//上に移動
if (IsSpace(pBanArr, CurrX, CurrY - 1)
&& IsSpace(pBanArr, CurrX + 1, CurrY - 1)) {
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[CurrX, CurrY - 1] = wkArr[CurrX + 1, CurrY - 1] = pPiece;
wkArr[CurrX, CurrY + 1] = wkArr[CurrX + 1, CurrY + 1] = '□';
WillReturn.Add(wkArr);
}
//下に移動
if (IsSpace(pBanArr, CurrX, CurrY + 2)
&& IsSpace(pBanArr, CurrX + 1, CurrY + 2)) {
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[CurrX, CurrY] = wkArr[CurrX + 1, CurrY] = '□';
wkArr[CurrX, CurrY + 2] = wkArr[CurrX + 1, CurrY + 2] = pPiece;
WillReturn.Add(wkArr);
}
//左に移動
if (IsSpace(pBanArr, CurrX - 1, CurrY)
&& IsSpace(pBanArr, CurrX - 1, CurrY + 1)) {
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[CurrX - 1, CurrY] = pPiece;
wkArr[CurrX - 1, CurrY + 1] = pPiece;
wkArr[CurrX + 1, CurrY] = wkArr[CurrX + 1, CurrY + 1] = '□';
WillReturn.Add(wkArr);
}
//右に移動
if (IsSpace(pBanArr, CurrX + 2, CurrY)
&& IsSpace(pBanArr, CurrX + 2, CurrY + 1)) {
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[CurrX + 2, CurrY] = pPiece;
wkArr[CurrX + 2, CurrY + 1] = pPiece;
wkArr[CurrX, CurrY] = wkArr[CurrX, CurrY + 1] = '□';
WillReturn.Add(wkArr);
}
return WillReturn;
}
//座標が空白かを判定
static bool IsSpace(char[,] pBanArr, int pX, int pY)
{
if (pX < 0 || UB < pX) return false;
if (pY < 0 || UB < pY) return false;
return pBanArr[pX, pY] == '□';
}
//盤面とピースを引数として、ピースの左上の座標を返す
static PointDef DerivePiecePoint(char[,] pBanArr, char pPiece)
{
for (int LoopY = 0; LoopY <= UB; LoopY++) {
for (int LoopX = 0; LoopX <= UB; LoopX++) {
if (pBanArr[LoopX, LoopY] == pPiece) {
return new PointDef() { X = LoopX, Y = LoopY };
}
}
}
return new PointDef() { X = -1, Y = -1 };
}
//盤面をハッシュ値に変換
static decimal GetHash(char[,] pBanArr)
{
decimal WillReturn = 0;
foreach (char EachPiece in mPieceArr) {
bool WillBreak = false;
for (int X = 0; X <= UB; X++) {
for (int Y = 0; Y <= UB; Y++) {
if (pBanArr[X, Y] != EachPiece) continue;
WillReturn *= (UB + 1); WillReturn += X;
WillReturn *= (UB + 1); WillReturn += Y;
WillBreak = true;
break;
}
if (WillBreak) break;
}
}
//7の28乗=459986536544739960976801なのでDecimal型ならオーバーフローしない
return WillReturn;
}
//盤面を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();
}
}
ラッシュアワーと違い、車は上下左右に動けます。 猛獣の巣も上下左右に動けます。 Q1 上のサンプル問題 Q2
Q3
