using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static System.Diagnostics.Stopwatch sw = System.Diagnostics.Stopwatch.StartNew();
static void Main()
{
string[] BanStrArr1 ={"AA*",
"AA*",
"AAA",
"AAA"};
Solve(BanStrArr1);
string[] BanStrArr2 ={"****A**",
"*AAAAA*",
"AAAAAA*",
"*AAAAA*",
"*AAAAA*",
"*AAAAA*",
"*AAAAA*",
"AAAAAAA",
"*AAAAA*"};
Solve(BanStrArr2);
}
static void Solve(string[] pBanStrArr)
{
char[,] wkBanArr = new char[pBanStrArr[0].Length, pBanStrArr.Length];
for (int LoopY = 0; LoopY <= pBanStrArr.GetUpperBound(0); LoopY++) {
for (int LoopX = 0; LoopX <= pBanStrArr[LoopY].Length - 1; LoopX++) {
wkBanArr[LoopX, LoopY] = pBanStrArr[LoopY][LoopX];
}
}
List<char[,]> AnswerArrList = ExecDFS(wkBanArr);
if (AnswerArrList.Count > 0) {
Console.WriteLine("解を発見。経過時間={0}", sw.Elapsed);
AnswerArrList.ForEach(X => PrintAnswer(X));
}
}
struct JyoutaiDef1
{
internal int Level;
internal char[,] BanArr;
internal HashSet<string> UsedFromPosSet; //使用済のFrom座標
}
//深さ優先探索で解を列挙
static List<char[,]> ExecDFS(char[,] pBanArr)
{
var WillReturn = new List<char[,]>();
//探索の開始座標を求める
int StaX, StaY;
DeriveStaPoint(pBanArr, out StaX, out StaY);
var stk = new Stack<JyoutaiDef1>();
JyoutaiDef1 WillPush;
WillPush.Level = 1;
WillPush.BanArr = (char[,])pBanArr.Clone();
WillPush.BanArr[StaX, StaY] = 'B';
WillPush.UsedFromPosSet = new HashSet<string>();
stk.Push(WillPush);
var VisitedSet = new HashSet<ulong>();
int NeedCnt = pBanArr.Cast<char>().Count(X => X == 'A') / 2;
while (stk.Count > 0) {
JyoutaiDef1 Popped = stk.Pop();
//クリア判定
if (Popped.Level == NeedCnt) {
if (IsGoudouZukei(Popped.BanArr))
WillReturn.Add(Popped.BanArr);
continue;
}
int UB_X = pBanArr.GetUpperBound(0);
int UB_Y = pBanArr.GetUpperBound(1);
var wkUsedFromPos = new HashSet<string>();
for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
if (Popped.BanArr[LoopX, LoopY] != 'B') continue;
//使用済のFrom座標ならContinue
if (Popped.UsedFromPosSet.Contains(string.Format("({0},{1})", LoopX, LoopY)))
continue;
Action<int, int> PushSyori = (pX, pY) =>
{
//特殊枝切り 長さが9になったら枝切り
if (pY == 8) return;
if (pX < 0 || UB_X < pX) return;
if (pY < 0 || UB_Y < pY) return;
if (Popped.BanArr[pX, pY] != 'A') return;
WillPush.Level = Popped.Level + 1;
WillPush.BanArr = (char[,])Popped.BanArr.Clone();
WillPush.BanArr[pX, pY] = 'B';
//特殊枝切り 閉路ができたら枝切り
int RestCnt = 0;
if (pX == 1 && pY == 2) RestCnt = 1;
if (pX == 1 && pY == 7) RestCnt = 1;
if (pX == 5 && pY == 7) RestCnt = 1;
if (IsBundanA(WillPush.BanArr, RestCnt)) return;
WillPush.UsedFromPosSet = new HashSet<string>(Popped.UsedFromPosSet);
WillPush.UsedFromPosSet.UnionWith(wkUsedFromPos);
if (VisitedSet.Add(BanToULong(WillPush.BanArr)))
stk.Push(WillPush);
};
PushSyori(LoopX, LoopY - 1);
PushSyori(LoopX, LoopY + 1);
PushSyori(LoopX - 1, LoopY);
PushSyori(LoopX + 1, LoopY);
wkUsedFromPos.Add(string.Format("({0},{1})", LoopX, LoopY));
}
}
}
return WillReturn;
}
//探索の開始座標を求める
static void DeriveStaPoint(char[,] pBanArr, out int pStaX, out int pStaY)
{
pStaX = pStaY = -1;
for (int LoopY = 0; LoopY <= pBanArr.GetUpperBound(1); LoopY++) {
for (int LoopX = 0; LoopX <= pBanArr.GetUpperBound(0); LoopX++) {
if (pBanArr[LoopX, LoopY] == 'A') {
pStaX = LoopX; pStaY = LoopY;
return;
}
}
}
}
//盤面をULong型で表現
static ulong BanToULong(char[,] pBanArr)
{
var sb = new System.Text.StringBuilder();
for (int X = 0; X <= pBanArr.GetUpperBound(0); X++) {
for (int Y = 0; Y <= pBanArr.GetUpperBound(1); Y++) {
char CurrChar = pBanArr[X, Y];
if (CurrChar == 'A') sb.Append('0');
if (CurrChar == 'B') sb.Append('1');
}
}
return Convert.ToUInt64(sb.ToString(), 2);
}
struct JyoutaiDef2
{
internal int CurrX;
internal int CurrY;
}
//Aが分断されてるかを判定
static bool IsBundanA(char[,] pBanArr, int pRestCnt)
{
//探索の開始座標を求める
int StaX, StaY;
DeriveStaPoint(pBanArr, out StaX, out StaY);
var stk = new Stack<JyoutaiDef2>();
JyoutaiDef2 WillPush;
WillPush.CurrX = StaX;
WillPush.CurrY = StaY;
stk.Push(WillPush);
var VisitedSet = new HashSet<string>();
VisitedSet.Add(string.Format("({0},{1})", StaX, StaY));
while (stk.Count > 0) {
JyoutaiDef2 Popped = stk.Pop();
Action<int, int> PushSyori = (pNewX, pNewY) =>
{
if (pNewX < 0 || pBanArr.GetUpperBound(0) < pNewX) return;
if (pNewY < 0 || pBanArr.GetUpperBound(1) < pNewY) return;
if (pBanArr[pNewX, pNewY] != 'A') return;
if (VisitedSet.Add(string.Format("({0},{1})", pNewX, pNewY)) == false)
return;
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 VisitedSet.Count + pRestCnt < pBanArr.Cast<char>().Count(X => X == 'A');
}
//AとBで合同な図形かを判定
static bool IsGoudouZukei(char[,] pBanArr)
{
//Aを切り出す
char[,] ArrA = ExecReduceArr('A', pBanArr);
//Bを切り出す
char[,] ArrB = ExecReduceArr('B', pBanArr);
//長い方の長さと、短い方の長さが一致するのが必要条件
int ArrA_UB_X = ArrA.GetUpperBound(0);
int ArrA_UB_Y = ArrA.GetUpperBound(1);
int ArrB_UB_X = ArrB.GetUpperBound(0);
int ArrB_UB_Y = ArrB.GetUpperBound(1);
if (Math.Min(ArrA_UB_X, ArrA_UB_Y) != Math.Min(ArrB_UB_X, ArrB_UB_Y))
return false;
if (Math.Max(ArrA_UB_X, ArrA_UB_Y) != Math.Max(ArrB_UB_X, ArrB_UB_Y))
return false;
//AとBを比較
if (IsGoudouArr(ArrA, ArrB)) return true;
//Aの90度回転
ArrA = Kaiten90do(ArrA);
if (IsGoudouArr(ArrA, ArrB)) return true;
//Aの180度回転
ArrA = Kaiten90do(ArrA);
if (IsGoudouArr(ArrA, ArrB)) return true;
//Aの270度回転
ArrA = Kaiten90do(ArrA);
if (IsGoudouArr(ArrA, ArrB)) return true;
//Aの左右反転
ArrA = SayuuHanten(ArrA);
if (IsGoudouArr(ArrA, ArrB)) return true;
//Aの左右反転の90度回転
ArrA = Kaiten90do(ArrA);
if (IsGoudouArr(ArrA, ArrB)) return true;
//Aの左右反転の180度回転
ArrA = Kaiten90do(ArrA);
if (IsGoudouArr(ArrA, ArrB)) return true;
//Aの左右反転の270度回転
ArrA = Kaiten90do(ArrA);
if (IsGoudouArr(ArrA, ArrB)) return true;
return false;
}
//指定した文字を含んだ、最小の2次元配列に縮小する
static char[,] ExecReduceArr(char pTargetChar, char[,] pBanArr)
{
char[,] 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 char[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] = wkChar;
else WillReturnArr[X, Y] = '*';
}
}
return WillReturnArr;
}
//合同かを判定
static bool IsGoudouArr(char[,] pBanArrA, char[,] pBanArrB)
{
int ArrA_UB_X = pBanArrA.GetUpperBound(0);
int ArrA_UB_Y = pBanArrA.GetUpperBound(1);
int ArrB_UB_X = pBanArrB.GetUpperBound(0);
int ArrB_UB_Y = pBanArrB.GetUpperBound(1);
//X軸の要素数チェック
if (ArrA_UB_X != ArrB_UB_X) return false;
//Y軸の要素数チェック
if (ArrA_UB_Y != ArrB_UB_Y) return false;
for (int X = 0; X <= ArrA_UB_X; X++) {
for (int Y = 0; Y <= ArrA_UB_Y; Y++) {
if (pBanArrA[X, Y] == 'A' && pBanArrB[X, Y] != 'B')
return false;
if (pBanArrA[X, Y] != 'A' && pBanArrB[X, Y] == 'B')
return false;
}
}
return true;
}
//右に90度回転させた盤面を返す
static char[,] Kaiten90do(char[,] pBanArr)
{
char[,] WillReturn = new char[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 char[,] SayuuHanten(char[,] pBanArr)
{
char[,] WillReturn = new char[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 PrintAnswer(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());
}
}
