using System;
using System.Collections.Generic;
class Program
{
const int UB_X = 5;
const int UB_Y = 4;
struct PointDef
{
internal int X;
internal int Y;
}
struct JyoutaiDef
{
internal char[,] BanArr;
internal List<string> Log;
}
static void Main()
{
string[] InitArr ={"□□□□板板",
"□犬犬□□■",
"■□犬犬犬□",
"□茶犬赤犬黄",
"□犬犬■犬犬"};
var Que = new Queue<JyoutaiDef>();
JyoutaiDef WillEnqueue;
WillEnqueue.BanArr = new char[UB_X + 1, UB_Y + 1];
for (int X = 0; X <= UB_X; X++) {
for (int Y = 0; Y <= UB_Y; Y++) {
WillEnqueue.BanArr[X, Y] = InitArr[Y][X];
}
}
WillEnqueue.Log = new List<string>();
WillEnqueue.Log.Add(BanToStr(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);
Console.WriteLine(Dequeued.Log[I]);
}
return;
}
foreach (char EachPiece in "板茶赤黄犬") {
//盤面とピースを引数として、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.Log = new List<string>(Dequeued.Log);
WillEnqueue.Log.Add(BanToStr(WillEnqueue.BanArr));
Que.Enqueue(WillEnqueue);
}
}
}
}
//クリア判定
static bool IsClear(char[,] pBanArr)
{
if (pBanArr[3, 3] != '黄') return false;
if (pBanArr[5, 3] != '赤') return false;
return true;
}
//盤面とピースを引数として、1手後の盤面のListを返す
static List<char[,]> DeriveMovedBanArrList(char[,] pBanArr, char pPiece)
{
var WillReturn = new List<char[,]>();
var Stk = new Stack<char[,]>();
char[,] WillPush;
WillPush = pBanArr;
Stk.Push(WillPush);
var VisitedSet = new HashSet<string>();
while (Stk.Count > 0) {
char[,] Popped = Stk.Pop();
List<char[,]> MovedBanArrList = DeriveMovedBanArrListHelper(Popped, pPiece);
foreach (char[,] EachBanArr in MovedBanArrList) {
string CurrHash = GetHash(EachBanArr);
if (CurrHash == GetHash(pBanArr)) continue;
if (VisitedSet.Add(CurrHash) == false) continue;
WillReturn.Add(EachBanArr);
Stk.Push(EachBanArr);
}
}
return WillReturn;
}
//盤面とピースを引数として、移動後の盤面のListを返す
static List<char[,]> DeriveMovedBanArrListHelper(char[,] pBanArr, char pPiece)
{
var WillReturn = new List<char[,]>();
PointDef wkPiecePoint = DerivePiecePoint(pBanArr, pPiece);
int CurrX = wkPiecePoint.X;
int CurrY = wkPiecePoint.Y;
if (pPiece == '板') {
//上に移動
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] = '板';
wkArr[CurrX, CurrY] = wkArr[CurrX + 1, CurrY] = '□';
WillReturn.Add(wkArr);
}
//下に移動
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] = '板';
wkArr[CurrX, CurrY] = wkArr[CurrX + 1, CurrY] = '□';
WillReturn.Add(wkArr);
}
//左に移動
if (IsSpace(pBanArr, CurrX - 1, CurrY)) {
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[CurrX - 1, CurrY] = '板';
wkArr[CurrX + 1, CurrY] = '□';
WillReturn.Add(wkArr);
}
//右に移動
if (IsSpace(pBanArr, CurrX + 2, CurrY)) {
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[CurrX + 2, CurrY] = '板';
wkArr[CurrX, CurrY] = '□';
WillReturn.Add(wkArr);
}
}
if (pPiece == '茶' || pPiece == '赤' || pPiece == '黄') {
//上に移動
if (IsSpace(pBanArr, CurrX, CurrY - 1)) {
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[CurrX, CurrY - 1] = pPiece; wkArr[CurrX, CurrY] = '□';
WillReturn.Add(wkArr);
}
//下に移動
if (IsSpace(pBanArr, CurrX, CurrY + 1)) {
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[CurrX, CurrY + 1] = pPiece; wkArr[CurrX, CurrY] = '□';
WillReturn.Add(wkArr);
}
//左に移動
if (IsSpace(pBanArr, CurrX - 1, CurrY)) {
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[CurrX - 1, CurrY] = pPiece; wkArr[CurrX, CurrY] = '□';
WillReturn.Add(wkArr);
}
//右に移動
if (IsSpace(pBanArr, CurrX + 1, CurrY)) {
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[CurrX + 1, CurrY] = pPiece; wkArr[CurrX, CurrY] = '□';
WillReturn.Add(wkArr);
}
}
//上に移動
if (pPiece == '犬' && CurrX == 1 && CurrY == 1) {
bool CanMove = true;
if (IsSpace(pBanArr, 1, 0) == false) CanMove = false;
if (IsSpace(pBanArr, 2, 0) == false) CanMove = false;
if (IsSpace(pBanArr, 3, 1) == false) CanMove = false;
if (IsSpace(pBanArr, 4, 1) == false) CanMove = false;
if (IsSpace(pBanArr, 5, 3) == false) CanMove = false;
if (CanMove) {
char[,] wkArr = (char[,])pBanArr.Clone();
SetDog(wkArr, 1, 0);
wkArr[1, 1] = pBanArr[1, 2];
wkArr[1, 2] = pBanArr[1, 3];
wkArr[3, 2] = '□';
wkArr[1, 4] = '□'; wkArr[2, 4] = '□';
wkArr[4, 4] = '□'; wkArr[5, 4] = '□';
WillReturn.Add(wkArr);
}
}
//下に移動
if (pPiece == '犬' && CurrX == 1 && CurrY == 0) {
bool CanMove = true;
if (IsSpace(pBanArr, 3, 2) == false) CanMove = false;
if (IsSpace(pBanArr, 1, 4) == false) CanMove = false;
if (IsSpace(pBanArr, 2, 4) == false) CanMove = false;
if (IsSpace(pBanArr, 4, 4) == false) CanMove = false;
if (IsSpace(pBanArr, 5, 4) == false) CanMove = false;
if (CanMove) {
char[,] wkArr = (char[,])pBanArr.Clone();
SetDog(wkArr, 1, 1);
wkArr[1, 0] = '□'; wkArr[2, 0] = '□';
wkArr[3, 1] = '□'; wkArr[4, 1] = '□';
wkArr[1, 2] = pBanArr[1, 1];
wkArr[1, 3] = pBanArr[1, 2];
wkArr[5, 3] = '□';
WillReturn.Add(wkArr);
}
}
//左に移動
if (pPiece == '犬' && CurrX == 1 && CurrY == 0) {
bool CanMove = true;
if (IsSpace(pBanArr, 0, 0) == false) CanMove = false;
if (IsSpace(pBanArr, 1, 1) == false) CanMove = false;
if (IsSpace(pBanArr, 1, 2) == false) CanMove = false;
if (IsSpace(pBanArr, 0, 3) == false) CanMove = false;
if (CanMove) {
char[,] wkArr = (char[,])pBanArr.Clone();
SetDog(wkArr, 0, 0);
wkArr[2, 0] = '□';
wkArr[4, 1] = '□';
wkArr[2, 2] = pBanArr[3, 2]; wkArr[4, 2] = '□';
wkArr[2, 3] = pBanArr[3, 3]; wkArr[5, 3] = '□';
WillReturn.Add(wkArr);
}
}
//右に移動
if (pPiece == '犬' && CurrX == 0 && CurrY == 0) {
bool CanMove = true;
if (IsSpace(pBanArr, 2, 0) == false) CanMove = false;
if (IsSpace(pBanArr, 4, 1) == false) CanMove = false;
if (IsSpace(pBanArr, 4, 2) == false) CanMove = false;
if (IsSpace(pBanArr, 5, 3) == false) CanMove = false;
if (CanMove) {
char[,] wkArr = (char[,])pBanArr.Clone();
SetDog(wkArr, 1, 0);
wkArr[0, 0] = '□';
wkArr[1, 1] = '□';
wkArr[1, 2] = '□'; wkArr[3, 2] = pBanArr[2, 2];
wkArr[0, 3] = '□'; wkArr[3, 3] = pBanArr[2, 3];
WillReturn.Add(wkArr);
}
}
return WillReturn;
}
//犬の左上座標を引数として、配列に犬を設定
static void SetDog(char[,] pBanArr, int pBaseX, int pBaseY)
{
pBanArr[pBaseX + 0, pBaseY] = '犬';
pBanArr[pBaseX + 1, pBaseY] = '犬';
pBanArr[pBaseX + 1, pBaseY + 1] = '犬';
pBanArr[pBaseX + 2, pBaseY + 1] = '犬';
pBanArr[pBaseX + 3, pBaseY + 1] = '犬';
pBanArr[pBaseX + 1, pBaseY + 2] = '犬';
pBanArr[pBaseX + 3, pBaseY + 2] = '犬';
pBanArr[pBaseX + 0, pBaseY + 3] = '犬';
pBanArr[pBaseX + 1, pBaseY + 3] = '犬';
pBanArr[pBaseX + 3, pBaseY + 3] = '犬';
pBanArr[pBaseX + 4, pBaseY + 3] = '犬';
}
//盤面とピースを引数として、ピースの左上の座標を返す
static PointDef DerivePiecePoint(char[,] pBanArr, char pPiece)
{
for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
if (pBanArr[LoopX, LoopY] == pPiece) {
return new PointDef() { X = LoopX, Y = LoopY };
}
}
}
return new PointDef() { X = -1, Y = -1 };
}
//座標が空白かを判定
static bool IsSpace(char[,] pBanArr, int pX, int pY)
{
if (pX < 0 || UB_X < pX) return false;
if (pY < 0 || UB_Y < pY) return false;
return pBanArr[pX, pY] == '□';
}
//ハッシュ値を求める
static string GetHash(char[,] pBanArr)
{
var sb = new System.Text.StringBuilder();
for (int X = 0; X <= UB_X; X++) {
for (int Y = 0; Y <= UB_Y; Y++) {
if (pBanArr[X, Y] == '■') continue;
sb.Append(pBanArr[X, Y]);
}
}
return sb.ToString();
}
//盤面をString型で表現
static string BanToStr(char[,] pBanArr)
{
var sb = new System.Text.StringBuilder();
for (int Y = 0; Y <= UB_Y; Y++) {
for (int X = 0; X <= UB_X; X++) {
sb.Append(pBanArr[X, Y]);
}
sb.AppendLine();
}
return sb.ToString();
}
}
犬、3つのボール、長方形のボード 合計5つのピースを動かして、 赤いボールと黄緑のボールの位置が入れ替わればクリアです。