using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
const int UB = 5 - 1;
static void Main()
{
var sw = System.Diagnostics.Stopwatch.StartNew();
List<char[,]> BanArrListA = ExecStampCut(InitBanArr(), 'A');
Console.WriteLine("Aの配置盤面は{0}通り", BanArrListA.Count);
var BanArrListB = new List<char[,]>();
BanArrListA.ForEach(X => BanArrListB.AddRange(ExecStampCut(X, 'B')));
Console.WriteLine("ABの配置盤面は{0}通り", BanArrListB.Count);
var BanArrListD = new List<char[,]>();
BanArrListB.ForEach(X => BanArrListD.AddRange(ExecStampCut(X, 'C')));
RemoveKaitenkai();
for (int I = 0; I <= mAnswerInfoList.Count - 1; I++) {
Console.WriteLine("解{0}", I + 1);
PrintBan(mAnswerInfoList[I].BanArr_5_5);
PrintBan(mAnswerInfoList[I].BanArr_4_4);
PrintBan(mAnswerInfoList[I].BanArr_3_3);
}
Console.WriteLine("経過時間={0}", sw.Elapsed);
}
struct AnswerInfoDef
{
internal char[,] BanArr_5_5;
internal char[,] BanArr_4_4;
internal char[,] BanArr_3_3;
internal Dictionary<char, bool[,]> PieceArrDict;
}
static List<AnswerInfoDef> mAnswerInfoList = new List<AnswerInfoDef>();
struct JyoutaiDefStampCut
{
internal char[,] BanArr;
internal HashSet<string> UsedPosSet;
}
//深さ優先探索で切手を切る
static List<char[,]> ExecStampCut(char[,] pBanArr, char pStampID)
{
var WillReturn = new List<char[,]>();
var Stk = new Stack<JyoutaiDefStampCut>();
JyoutaiDefStampCut WillPush;
WillPush.BanArr = pBanArr;
if (pStampID == 'A') WillPush.BanArr[0, 0] = 'A';
if (pStampID == 'B') WillPush.BanArr[UB, 0] = 'B';
if (pStampID == 'C') WillPush.BanArr[0, UB] = 'C';
WillPush.UsedPosSet = new HashSet<string>();
Stk.Push(WillPush);
var VisitedSet = new HashSet<string>();
while (Stk.Count > 0) {
JyoutaiDefStampCut Popped = Stk.Pop();
if (pStampID == 'A' && IsValidEndA(Popped.BanArr))
WillReturn.Add(Popped.BanArr);
if (pStampID == 'B' && IsValidEndB(Popped.BanArr))
WillReturn.Add(Popped.BanArr);
if (pStampID == 'C' && IsValidEndC(Popped.BanArr))
WillReturn.Add(Popped.BanArr);
var wkUsedPosSet = new HashSet<string>();
Action<int, int> PushSyori = (pNewX, pNewY) =>
{
if (pNewX < 0 || UB < pNewX) return;
if (pNewY < 0 || UB < pNewY) return;
if (Popped.BanArr[pNewX, pNewY] != ' ') return;
WillPush.BanArr = (char[,])Popped.BanArr.Clone();
WillPush.BanArr[pNewX, pNewY] = pStampID;
if (WillEdakiri(WillPush.BanArr)) return;
if (VisitedSet.Add(GetHash(WillPush.BanArr)) == false) return;
WillPush.UsedPosSet = new HashSet<string>(Popped.UsedPosSet);
WillPush.UsedPosSet.UnionWith(wkUsedPosSet);
Stk.Push(WillPush);
};
for (int X = 0; X <= UB; X++) {
for (int Y = 0; Y <= UB; Y++) {
if (Popped.BanArr[X, Y] == pStampID) {
PushSyori(X, Y - 1);
PushSyori(X, Y + 1);
PushSyori(X - 1, Y);
PushSyori(X + 1, Y);
wkUsedPosSet.Add(string.Format("({0},{1})", X, Y));
}
}
}
}
return WillReturn;
}
//初期盤面を返す
static char[,] InitBanArr()
{
char[,] WillReturn = new char[UB + 1, UB + 1];
for (int X = 0; X <= UB; X++)
for (int Y = 0; Y <= UB; Y++)
WillReturn[X, Y] = ' ';
return WillReturn;
}
//枝切り判定
static bool WillEdakiri(char[,] pBanArr)
{
for (int X = 0; X <= UB; X++) {
if (pBanArr[X, UB] == 'A') return true;
if (pBanArr[X, UB] == 'B') return true;
if (pBanArr[X, 0] == 'C') return true;
if (pBanArr[X, 0] == 'D') return true;
}
for (int Y = 0; Y <= UB; Y++) {
if (pBanArr[0, Y] == 'B') return true;
if (pBanArr[0, Y] == 'D') return true;
if (pBanArr[UB, Y] == 'A') return true;
if (pBanArr[UB, Y] == 'C') return true;
}
return false;
}
//盤面をハッシュ値に変換
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();
}
struct JyoutaiDefUnionFind
{
internal int CurrX;
internal int CurrY;
}
//分断された空白の有無を返す
static bool ExecUnionFind(char[,] pBanArr)
{
var Stk = new Stack<JyoutaiDefUnionFind>();
JyoutaiDefUnionFind WillPush;
var VisitedSet = new HashSet<string>();
Action<int, int> wkAct = (pStaX, pStaY) =>
{
if (pBanArr[pStaX, pStaY] == ' ') {
WillPush.CurrX = pStaX;
WillPush.CurrY = pStaY;
Stk.Push(WillPush);
VisitedSet.Add(string.Format("({0},{1})", pStaX, pStaY));
}
};
wkAct(UB, 0); wkAct(0, UB); wkAct(UB, UB);
while (Stk.Count > 0) {
JyoutaiDefUnionFind Popped = Stk.Pop();
Action<int, int> PushSyori = (pNewX, pNewY) =>
{
if (pNewX < 0 || UB < pNewX) return;
if (pNewY < 0 || UB < pNewY) return;
if (pBanArr[pNewX, pNewY] != ' ') return;
if (VisitedSet.Add(string.Format("({0},{1})", pNewX, pNewY))) {
WillPush.CurrX = pNewX;
WillPush.CurrY = pNewY;
Stk.Push(WillPush);
}
};
PushSyori(Popped.CurrX, Popped.CurrY - 1);
PushSyori(Popped.CurrX, Popped.CurrY + 1);
PushSyori(Popped.CurrX - 1, Popped.CurrY);
PushSyori(Popped.CurrX + 1, Popped.CurrY);
}
return pBanArr.Cast<char>().Count(A => A == ' ') > VisitedSet.Count;
}
//有効な盤面かを判定(Aの切り出し後)
static bool IsValidEndA(char[,] pBanArr)
{
if (pBanArr[2, 2] != 'A') return false;
if (ExecUnionFind(pBanArr)) return false;
return true;
}
//有効な盤面かを判定(Bの切り出し後)
static bool IsValidEndB(char[,] pBanArr)
{
for (int X = 1; X <= UB - 1; X++)
if (pBanArr[X, 0] == ' ') return false;
if (ExecUnionFind(pBanArr)) return false;
return true;
}
//有効な盤面かを判定(Cの切り出し後)
static bool IsValidEndC(char[,] pBanArr)
{
for (int Y = 1; Y <= UB - 1; Y++)
if (pBanArr[0, Y] == ' ') return false;
if (ExecUnionFind(pBanArr)) return false;
char[,] BanArrFillD = (char[,])pBanArr.Clone();
for (int X = 0; X <= UB; X++)
for (int Y = 0; Y <= UB; Y++)
if (BanArrFillD[X, Y] == ' ')
BanArrFillD[X, Y] = 'D';
//動的計画法で、和が9の組み合わせが存在するかを判定
char[] wkArr = BanArrFillD.Cast<char>().ToArray();
int CntA = wkArr.Count(X => X == 'A');
int CntB = wkArr.Count(X => X == 'B');
int CntC = wkArr.Count(X => X == 'C');
int CntD = wkArr.Count(X => X == 'D');
bool[] DPArr = new bool[25 + 1];
DPArr[0] = true;
foreach (int EachInt in new int[] { CntA, CntB, CntC, CntD })
for (int I = DPArr.GetUpperBound(0); 0 <= I; I--)
if (DPArr[I]) DPArr[I + EachInt] = true;
if (DPArr[9] == false) return false;
//3*3と4*4に敷き詰め可能かを判定
return CanShikitume(BanArrFillD);
}
struct JyoutaiDefShikitume
{
internal List<char[,]> BanArrList;
internal int CurrBanInd;
internal int CurrX;
internal int CurrY;
internal HashSet<char> UsePieceSet;
}
//3*3と4*4に敷き詰め可能かを判定
static bool CanShikitume(char[,] pBanArrFillD)
{
bool[,] AArr = ExecReduceArr('A', pBanArrFillD);
bool[,] BArr = ExecReduceArr('B', pBanArrFillD);
bool[,] CArr = ExecReduceArr('C', pBanArrFillD);
bool[,] DArr = ExecReduceArr('D', pBanArrFillD);
//3*3を敷き詰める必要条件の判定
int MensekiSum = 0;
Action<bool[,]> KasanAct = pArr =>
{
int UB_X = pArr.GetUpperBound(0);
int UB_Y = pArr.GetUpperBound(1);
if (UB_X > 2) return;
if (UB_Y > 2) return;
MensekiSum += (UB_X + 1) * (UB_Y + 1);
};
KasanAct(AArr); KasanAct(BArr); KasanAct(CArr); KasanAct(DArr);
if (MensekiSum < 3 * 3) return false;
//ピースごとの配置候補
char[] PieceNameArr = { 'A', 'B', 'C', 'D' };
var HaitiKouhoListDict = new Dictionary<char, bool[,]>();
HaitiKouhoListDict['A'] = AArr;
HaitiKouhoListDict['B'] = BArr;
HaitiKouhoListDict['C'] = CArr;
HaitiKouhoListDict['D'] = DArr;
var Stk = new Stack<JyoutaiDefShikitume>();
JyoutaiDefShikitume WillPush;
WillPush.BanArrList = new List<char[,]>();
Func<int, char[,]> CreateArrFunc = (pLength) =>
{
char[,] WillReturnArr = new char[pLength, pLength];
for (int X = 0; X <= pLength - 1; X++)
for (int Y = 0; Y <= pLength - 1; Y++)
WillReturnArr[X, Y] = ' ';
return WillReturnArr;
};
WillPush.BanArrList.Add(CreateArrFunc(4));
WillPush.BanArrList.Add(CreateArrFunc(3));
WillPush.CurrBanInd = 0;
WillPush.CurrX = WillPush.CurrY = 0;
WillPush.UsePieceSet = new HashSet<char>();
Stk.Push(WillPush);
while (Stk.Count > 0) {
JyoutaiDefShikitume Popped = Stk.Pop();
//クリア判定
if (Popped.BanArrList[Popped.CurrBanInd].Cast<char>().All(X => X != ' ')) {
if (++Popped.CurrBanInd > 1) {
AnswerInfoDef WillAdd;
WillAdd.BanArr_3_3 = Popped.BanArrList[1];
WillAdd.BanArr_4_4 = Popped.BanArrList[0];
WillAdd.BanArr_5_5 = pBanArrFillD;
WillAdd.PieceArrDict = new Dictionary<char, bool[,]>();
WillAdd.PieceArrDict['A'] = AArr;
WillAdd.PieceArrDict['B'] = BArr;
WillAdd.PieceArrDict['C'] = CArr;
WillAdd.PieceArrDict['D'] = DArr;
mAnswerInfoList.Add(WillAdd);
return true;
}
Popped.CurrX = Popped.CurrY = 0;
}
//X座標の繰上げ処理
if (Popped.CurrX > Popped.BanArrList[Popped.CurrBanInd].GetUpperBound(0)) {
Popped.CurrX = 0;
Popped.CurrY++;
}
//最終行を超えた場合
if (Popped.CurrY > Popped.BanArrList[Popped.CurrBanInd].GetUpperBound(1))
continue;
foreach (char EachPiece in PieceNameArr) {
if (Popped.UsePieceSet.Contains(EachPiece)) continue;
//ピースの配置候補
bool[,] HaitiKouho = HaitiKouhoListDict[EachPiece];
//現在のマス目が空白の場合は、マス目を埋める必要あり
if (Popped.BanArrList[Popped.CurrBanInd][Popped.CurrX, Popped.CurrY] == ' ')
if (HaitiKouho[0, 0] == false) continue;
//マス目にピースを埋めれない候補ならContinue
if (CanFillPiece(HaitiKouho, Popped.CurrX, Popped.CurrY,
Popped.BanArrList[Popped.CurrBanInd]) == false)
continue;
//ピースを配置する経路のPush処理
WillPush.CurrBanInd = Popped.CurrBanInd;
WillPush.BanArrList = new List<char[,]>(Popped.BanArrList);
WillPush.BanArrList[WillPush.CurrBanInd] =
(char[,])Popped.BanArrList[Popped.CurrBanInd].Clone();
WillPush.CurrX = Popped.CurrX;
WillPush.CurrY = Popped.CurrY;
for (int X = 0; X <= HaitiKouho.GetUpperBound(0); X++) {
for (int Y = 0; Y <= HaitiKouho.GetUpperBound(1); Y++) {
if (HaitiKouho[X, Y] == false) continue;
WillPush.BanArrList[WillPush.CurrBanInd]
[Popped.CurrX + X, Popped.CurrY + Y] = EachPiece;
}
}
WillPush.UsePieceSet = new HashSet<char>(Popped.UsePieceSet);
WillPush.UsePieceSet.Add(EachPiece);
Stk.Push(WillPush);
}
//現在のマス目が空白でない場合は、ピースを配置しない経路のPush
if (Popped.BanArrList[Popped.CurrBanInd][Popped.CurrX, Popped.CurrY] != ' ') {
WillPush.CurrBanInd = Popped.CurrBanInd;
WillPush.BanArrList = Popped.BanArrList;
WillPush.CurrX = Popped.CurrX + 1;
WillPush.CurrY = Popped.CurrY;
WillPush.UsePieceSet = Popped.UsePieceSet;
Stk.Push(WillPush);
}
}
return false;
}
//指定した文字を含んだ、最小の2次元配列に縮小する
static bool[,] ExecReduceArr(char pTargetChar, char[,] pBanArr)
{
bool[,] WillReturnArr;
int XMin = pBanArr.GetUpperBound(0), YMin = pBanArr.GetUpperBound(1);
int XMax = 0, YMax = 0;
for (int X = 0; X <= pBanArr.GetUpperBound(0); X++) {
for (int Y = 0; Y <= pBanArr.GetUpperBound(1); Y++) {
if (pBanArr[X, Y] != pTargetChar) continue;
if (XMin > X) XMin = X;
if (YMin > Y) YMin = Y;
if (XMax < X) XMax = X;
if (YMax < Y) YMax = Y;
}
}
WillReturnArr = new bool[XMax - XMin + 1, YMax - YMin + 1];
for (int X = 0; X <= WillReturnArr.GetUpperBound(0); X++) {
for (int Y = 0; Y <= WillReturnArr.GetUpperBound(1); Y++) {
char wkChar = pBanArr[XMin + X, YMin + Y];
if (wkChar == pTargetChar)
WillReturnArr[X, Y] = true;
}
}
return WillReturnArr;
}
//マス目にピースを埋めれるか
static bool CanFillPiece(bool[,] pPieceMap, int pTargetX, int pTargetY, char[,] pBanArr)
{
if (pTargetX + pPieceMap.GetUpperBound(0) > pBanArr.GetUpperBound(0)) return false;
if (pTargetY + pPieceMap.GetUpperBound(1) > pBanArr.GetUpperBound(1)) return false;
for (int X = 0; X <= pPieceMap.GetUpperBound(0); X++)
for (int Y = 0; Y <= pPieceMap.GetUpperBound(1); Y++)
if (pPieceMap[X, Y] && pBanArr[pTargetX + X, pTargetY + Y] != ' ')
return false;
return true;
}
//回転解を除外する
static void RemoveKaitenkai()
{
for (int I = mAnswerInfoList.Count - 1; 1 <= I; I--) {
for (int J = 0; J <= I - 1; J++) {
if (IsSameDict(mAnswerInfoList[I].PieceArrDict,
mAnswerInfoList[J].PieceArrDict)) {
mAnswerInfoList.RemoveAt(I);
break;
}
}
}
}
//切り取った切手が、回転して同じになるかを判定
static bool IsSameDict(Dictionary<char, bool[,]> pDict1, Dictionary<char, bool[,]> pDict2)
{
var UsedPieceNameSet = new HashSet<char>();
foreach (var EachPair1 in pDict1) {
bool HasGoudou = false;
foreach (var EachPair2 in pDict2) {
if (UsedPieceNameSet.Contains(EachPair2.Key)) continue;
if (IsGoudouZukei(EachPair1.Value, EachPair2.Value)) {
UsedPieceNameSet.Add(EachPair2.Key);
HasGoudou = true;
break;
}
}
if (HasGoudou == false) return false;
}
return true;
}
//回転して合同な図形になるかを判定
static bool IsGoudouZukei(bool[,] pBanArr1, bool[,] pBanArr2)
{
//長い方の長さと、短い方の長さが一致するのが必要条件
int Arr1_UB_X = pBanArr1.GetUpperBound(0);
int Arr1_UB_Y = pBanArr1.GetUpperBound(1);
int Arr2_UB_X = pBanArr2.GetUpperBound(0);
int Arr2_UB_Y = pBanArr2.GetUpperBound(1);
if (Math.Min(Arr1_UB_X, Arr1_UB_Y) != Math.Min(Arr2_UB_X, Arr2_UB_Y))
return false;
if (Math.Max(Arr1_UB_X, Arr1_UB_Y) != Math.Max(Arr2_UB_X, Arr2_UB_Y))
return false;
pBanArr1 = (bool[,])pBanArr1.Clone();
//AとBを比較
if (IsGoudouArr(pBanArr1, pBanArr2)) return true;
//Aの90度回転
pBanArr1 = Kaiten90do(pBanArr1);
if (IsGoudouArr(pBanArr1, pBanArr2)) return true;
//Aの180度回転
pBanArr1 = Kaiten90do(pBanArr1);
if (IsGoudouArr(pBanArr1, pBanArr2)) return true;
//Aの270度回転
pBanArr1 = Kaiten90do(pBanArr1);
if (IsGoudouArr(pBanArr1, pBanArr2)) return true;
//Aの左右反転
pBanArr1 = SayuuHanten(pBanArr1);
if (IsGoudouArr(pBanArr1, pBanArr2)) return true;
//Aの左右反転の90度回転
pBanArr1 = Kaiten90do(pBanArr1);
if (IsGoudouArr(pBanArr1, pBanArr2)) return true;
//Aの左右反転の180度回転
pBanArr1 = Kaiten90do(pBanArr1);
if (IsGoudouArr(pBanArr1, pBanArr2)) return true;
//Aの左右反転の270度回転
pBanArr1 = Kaiten90do(pBanArr1);
if (IsGoudouArr(pBanArr1, pBanArr2)) return true;
return false;
}
//合同かを判定
static bool IsGoudouArr(bool[,] pBanArr1, bool[,] pBanArr2)
{
int Arr1_UB_X = pBanArr1.GetUpperBound(0);
int Arr1_UB_Y = pBanArr1.GetUpperBound(1);
int Arr2_UB_X = pBanArr2.GetUpperBound(0);
int Arr2_UB_Y = pBanArr2.GetUpperBound(1);
//X軸の要素数チェック
if (Arr1_UB_X != Arr2_UB_X) return false;
//Y軸の要素数チェック
if (Arr1_UB_Y != Arr2_UB_Y) return false;
for (int X = 0; X <= Arr1_UB_X; X++) {
for (int Y = 0; Y <= Arr1_UB_Y; Y++) {
if (pBanArr1[X, Y] != pBanArr2[X, Y])
return false;
}
}
return true;
}
//右に90度回転させた盤面を返す
static bool[,] Kaiten90do(bool[,] pBanArr)
{
bool[,] WillReturn = new bool[pBanArr.GetUpperBound(1) + 1,
pBanArr.GetUpperBound(0) + 1];
for (int X = 0; X <= WillReturn.GetUpperBound(0); X++) {
for (int Y = 0; Y <= WillReturn.GetUpperBound(1); Y++) {
WillReturn[X, Y] = pBanArr[Y, WillReturn.GetUpperBound(0) - X];
}
}
return WillReturn;
}
//左右反転させた盤面を返す
static bool[,] SayuuHanten(bool[,] pBanArr)
{
bool[,] WillReturn = new bool[pBanArr.GetUpperBound(0) + 1,
pBanArr.GetUpperBound(1) + 1];
for (int X = 0; X <= WillReturn.GetUpperBound(0); X++) {
for (int Y = 0; Y <= WillReturn.GetUpperBound(1); Y++) {
WillReturn[X, Y] = pBanArr[WillReturn.GetUpperBound(0) - X, Y];
}
}
return WillReturn;
}
//盤面を出力
static void PrintBan(char[,] pBanArr)
{
var sb = new System.Text.StringBuilder();
for (int Y = 0; Y <= pBanArr.GetUpperBound(1); Y++) {
for (int X = 0; X <= pBanArr.GetUpperBound(0); X++) {
sb.Append(pBanArr[X, Y]);
}
sb.AppendLine();
}
Console.WriteLine(sb.ToString());
}
}