using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
const int UB = 3;
struct PointDef
{
internal int X;
internal int Y;
}
struct JyoutaiDef
{
internal char[,] BanArr;
internal int Level;
internal List<string> Log;
}
static void Main()
{
string[] InitArr ={"１縦■■",
"２縦□■",
"■□横横",
"■■３４"};
var Stk = new Stack<JyoutaiDef>();
JyoutaiDef WillPush;
WillPush.BanArr = new char[UB + 1, UB + 1];
for (int X = 0; X <= UB; X++) {
for (int Y = 0; Y <= UB; Y++) {
WillPush.BanArr[X, Y] = InitArr[Y][X];
}
}
WillPush.Level = 0;
WillPush.Log = new List<string>();
WillPush.Log.Add(BanToStr(WillPush.BanArr));
Stk.Push(WillPush);
var MinTesuuDict = new Dictionary<string, int>();
MinTesuuDict.Add(GetHash(WillPush.BanArr), 0);
List<string> AnswerLog = null;
int AnswerLevel = 35;
while (Stk.Count > 0) {
JyoutaiDef Popped = Stk.Pop();
if (IsClear(Popped.BanArr)) {
if (AnswerLog == null && Popped.Level == AnswerLevel
|| Popped.Level < AnswerLevel) {
AnswerLog = Popped.Log;
AnswerLevel = Popped.Level;
}
continue;
}
if (Popped.Level + 1 > AnswerLevel) continue;
foreach (char EachPiece in "縦横１２３４盤") {
//盤面とピースを引数として、1手後の盤面のListを返す
List<char[,]> MovedBanArrList = DeriveMovedBanArrList(Popped.BanArr, EachPiece);
foreach (char[,] EachMovedBanArr in MovedBanArrList) {
WillPush.BanArr = EachMovedBanArr;
WillPush.Level = Popped.Level + 1;
//メモ化探索
int MinTesuu;
string Hash = GetHash(EachMovedBanArr);
if (MinTesuuDict.TryGetValue(Hash, out MinTesuu)) {
if (MinTesuu <= WillPush.Level) continue;
}
MinTesuuDict[Hash] = WillPush.Level;
WillPush.Log = new List<string>(Popped.Log);
WillPush.Log.Add(BanToStr(WillPush.BanArr));
Stk.Push(WillPush);
}
}
}
for (int I = 0; I <= AnswerLog.Count - 1; I++) {
Console.WriteLine("{0}手目", I);
Console.WriteLine(AnswerLog[I]);
}
}
//クリア判定
static bool IsClear(char[,] pBanArr)
{
char wkChar1 = pBanArr[0, 0];
char wkChar2 = pBanArr[0, 1];
char wkChar3 = pBanArr[2, 3];
char wkChar4 = pBanArr[3, 3];
if (wkChar1 != '３' && wkChar1 != '４') return false;
if (wkChar2 != '３' && wkChar2 != '４') return false;
if (wkChar3 != '１' && wkChar3 != '２') return false;
if (wkChar4 != '１' && wkChar4 != '２') 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)) {
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[CurrX, CurrY - 1] = '縦';
wkArr[CurrX, CurrY + 1] = '□';
WillReturn.Add(wkArr);
}
//下に移動
if (IsSpace(pBanArr, CurrX, CurrY + 2)) {
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[CurrX, CurrY + 2] = '縦';
wkArr[CurrX, CurrY] = '□';
WillReturn.Add(wkArr);
}
//左に移動
if (IsSpace(pBanArr, CurrX - 1, CurrY)
&& IsSpace(pBanArr, CurrX - 1, CurrY + 1)) {
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[CurrX - 1, CurrY] = wkArr[CurrX - 1, CurrY + 1] = '縦';
wkArr[CurrX, CurrY] = wkArr[CurrX, CurrY + 1] = '□';
WillReturn.Add(wkArr);
}
//右に移動
if (IsSpace(pBanArr, CurrX + 1, CurrY)
&& IsSpace(pBanArr, CurrX + 1, CurrY + 1)) {
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[CurrX + 1, CurrY] = wkArr[CurrX + 1, CurrY + 1] = '縦';
wkArr[CurrX, CurrY] = wkArr[CurrX, CurrY + 1] = '□';
WillReturn.Add(wkArr);
}
}
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 ("１２３４".Contains(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 == '盤' && CanSlideUe(pBanArr)) { //上にスライド
//内包しているピースセット
var NaihouPieceSet = new HashSet<char>();
Action<int, int> AddAct = (pX, pY) =>
{
if (pBanArr[pX, pY] != '□')
NaihouPieceSet.Add(pBanArr[pX, pY]);
};
AddAct(2, 1);
AddAct(2, 2); AddAct(3, 2);
AddAct(2, 3); AddAct(3, 3);
//連動しているピースセット
var RendouPieceSet = new HashSet<char>();
//横を最初に判定する
foreach (char EachPiece in NaihouPieceSet.OrderByDescending(X => X == '横')) {
if (IsRendou(pBanArr, EachPiece, true, RendouPieceSet)) {
RendouPieceSet.Add(EachPiece);
}
}
char[,] wkArr = (char[,])pBanArr.Clone();
Action<int, int> CopyAct = (pBaseX, pBaseY) =>
{
char wkPiece = pBanArr[pBaseX, pBaseY + 1];
//連動してない場合
if (RendouPieceSet.Contains(wkPiece) == false) {
return;
}
if (wkPiece == '横') {
//UBの場合は処理しない
if (pBaseX == UB) return;
wkArr[pBaseX, pBaseY] = '横';
wkArr[pBaseX, pBaseY + 1] = '□';
if (wkArr[pBaseX - 1, pBaseY + 1] == '横') {
wkArr[pBaseX - 1, pBaseY + 1] = '□';
wkArr[pBaseX - 1, pBaseY] = '横';
}
if (wkArr[pBaseX + 1, pBaseY + 1] == '横') {
wkArr[pBaseX + 1, pBaseY + 1] = '□';
wkArr[pBaseX + 1, pBaseY] = '横';
}
}
else {
wkArr[pBaseX, pBaseY] = wkPiece;
wkArr[pBaseX, pBaseY + 1] = '□';
}
};
CopyAct(2, 0);
CopyAct(2, 1); CopyAct(3, 1);
CopyAct(2, 2); CopyAct(3, 2);
if (wkArr[2, 0] == '■') wkArr[2, 0] = '□';
wkArr[3, 0] = '■';
wkArr[2, 3] = '■';
wkArr[3, 3] = '■';
WillReturn.Add(wkArr);
}
if (pPiece == '盤' && CanSlideShita(pBanArr)) { //下にスライド
//内包しているピースセット
var NaihouPieceSet = new HashSet<char>();
Action<int, int> AddAct = (pX, pY) =>
{
if (pBanArr[pX, pY] != '□')
NaihouPieceSet.Add(pBanArr[pX, pY]);
};
AddAct(2, 0);
AddAct(2, 1); AddAct(3, 1);
AddAct(2, 2); AddAct(3, 2);
//連動しているピースセット
var RendouPieceSet = new HashSet<char>();
//横を最初に判定する
foreach (char EachPiece in NaihouPieceSet.OrderByDescending(X => X == '横')) {
if (IsRendou(pBanArr, EachPiece, false, RendouPieceSet)) {
RendouPieceSet.Add(EachPiece);
}
}
char[,] wkArr = (char[,])pBanArr.Clone();
Action<int, int> CopyAct = (pBaseX, pBaseY) =>
{
char wkPiece = pBanArr[pBaseX, pBaseY - 1];
//連動してない場合
if (RendouPieceSet.Contains(wkPiece) == false) {
return;
}
if (wkPiece == '横') {
//UBの場合は処理しない
if (pBaseX == UB) return;
wkArr[pBaseX, pBaseY] = '横';
wkArr[pBaseX, pBaseY - 1] = '□';
if (wkArr[pBaseX - 1, pBaseY - 1] == '横') {
wkArr[pBaseX - 1, pBaseY - 1] = '□';
wkArr[pBaseX - 1, pBaseY] = '横';
}
if (wkArr[pBaseX + 1, pBaseY - 1] == '横') {
wkArr[pBaseX + 1, pBaseY - 1] = '□';
wkArr[pBaseX + 1, pBaseY] = '横';
}
}
else {
wkArr[pBaseX, pBaseY] = wkPiece;
wkArr[pBaseX, pBaseY - 1] = '□';
}
};
CopyAct(2, 3); CopyAct(3, 3);
CopyAct(2, 2); CopyAct(3, 2);
CopyAct(2, 1);
wkArr[2, 0] = '■';
wkArr[3, 1] = '■';
if (wkArr[2, 3] == '■') wkArr[2, 3] = '□';
if (wkArr[3, 3] == '■') wkArr[3, 3] = '□';
WillReturn.Add(wkArr);
}
return WillReturn;
}
//スライドした時に連動するかを判定
static bool IsRendou(char[,] pBanArr, char pPiece, bool pIsSlideUe, HashSet<char> pRendouPieceSet)
{
PointDef wkPiecePoint = DerivePiecePoint(pBanArr, pPiece);
int CurrX = wkPiecePoint.X;
int CurrY = wkPiecePoint.Y;
int HeniY = (pIsSlideUe ? 1 : -1);
var RendouXList = new List<int>();
if (pPiece == '横') {
if (CurrX == 1) {
RendouXList.Add(2);
}
if (CurrX == 2) {
RendouXList.Add(2);
RendouXList.Add(3);
}
}
else RendouXList.Add(CurrX);
while (true) {
CurrY += HeniY;
if (CurrY < 0 || UB < CurrY)
return RendouXList.Count > 0;
for (int I = RendouXList.Count - 1; 0 <= I; I--) {
if (pBanArr[RendouXList[I], CurrY] == '□')
RendouXList.RemoveAt(I);
}
if (pBanArr[CurrX, CurrY] == '横')
return pRendouPieceSet.Contains('横');
}
}
//盤の右半分が、上にスライド可能かを判定
static bool CanSlideUe(char[,] pBanArr)
{
if (pBanArr[2, 0] != '■') return false;
if (pBanArr[3, 0] != '■') return false;
PointDef wkPiecePoint = DerivePiecePoint(pBanArr, '横');
int YokoBouX = wkPiecePoint.X;
int YokoBouY = wkPiecePoint.Y;
if (YokoBouX == 1 && YokoBouY == 1) {
if (pBanArr[2, 2] == '□') return true;
if (pBanArr[2, 3] == '□') return true;
if (pBanArr[1, 0] == '□') return true;
return false;
}
if (YokoBouX == 1 && YokoBouY == 2) {
if (pBanArr[2, 3] == '□') return true;
if (pBanArr[1, 1] == '□') return true;
return false;
}
return true;
}
//盤の右半分が、下にスライド可能かを判定
static bool CanSlideShita(char[,] pBanArr)
{
if (pBanArr[2, 3] != '■') return false;
if (pBanArr[3, 3] != '■') return false;
PointDef wkPiecePoint = DerivePiecePoint(pBanArr, '横');
int YokoBouX = wkPiecePoint.X;
int YokoBouY = wkPiecePoint.Y;
if (YokoBouX == 1 && YokoBouY == 0) {
if (pBanArr[1, 1] == '□') return true;
return false;
}
if (YokoBouX == 1 && YokoBouY == 1) {
if (pBanArr[2, 0] == '□') return true;
if (pBanArr[1, 2] == '□') return true;
return false;
}
if (YokoBouX == 1 && YokoBouY == 2) {
if (pBanArr[2, 0] == '□') return true;
if (pBanArr[2, 1] == '□') return true;
return false;
}
return true;
}
//盤面とピースを引数として、ピースの左上の座標を返す
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 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 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();
}
//盤面を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();
}
}
枠の中に大きなピースが2つ、 長方形のピースが2つある中に、 赤と黄緑の丸いピースが2個ずつ入っています。 この丸いピースの位置を入れかえてください。