using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static System.Diagnostics.Stopwatch sw = System.Diagnostics.Stopwatch.StartNew();
const int UB_X = 12;
const int UB_Y = 6;
struct JyoutaiDef
{
internal int CoinCnt;
internal int CurrX;
internal int CurrY;
internal char[,] BanArr;
internal bool IsSetCoin;
}
//F 埋立マス
//S 空白マス
//- コインを置けるマス
//* コインを置いたマス
static void Main()
{
var stk = new Stack<JyoutaiDef>();
JyoutaiDef WillPush;
WillPush.CoinCnt = 0;
WillPush.CurrX = WillPush.CurrY = 0;
string[] wkStrArr ={"SSS-F-F-F-SSS",
"SS-F-F-F-F-SS",
"S-F-F-F-F-F-S",
"-F-F-F-F-F-F-",
"S-F-F-F-F-F-S",
"SS-F-F-F-F-SS",
"SSS-F-F-F-SSS"};
WillPush.BanArr = new char[UB_X + 1, UB_Y + 1];
for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
WillPush.BanArr[LoopX, LoopY] = wkStrArr[LoopY][LoopX];
}
}
WillPush.IsSetCoin = false;
stk.Push(WillPush);
int AnswerCoinCnt = 0;
var AnswerBanArrList = new List<char[,]>();
while (stk.Count > 0) {
JyoutaiDef Popped = stk.Pop();
if (Popped.IsSetCoin) {
if (AnswerCoinCnt < Popped.CoinCnt) {
Console.WriteLine("コインの枚数={0}の解候補を発見。経過時間={1}",
Popped.CoinCnt, sw.Elapsed);
AnswerCoinCnt = Popped.CoinCnt;
AnswerBanArrList.Clear();
}
if (AnswerCoinCnt == Popped.CoinCnt) {
AnswerBanArrList.Add(Popped.BanArr);
}
}
//下限値枝切り
int RestHyphenCnt =
DeriveRestHyphenCnt(Popped.CurrX, Popped.CurrY, Popped.BanArr);
if (Popped.CoinCnt + RestHyphenCnt < AnswerCoinCnt)
continue;
//X座標の繰上げ処理
if (Popped.CurrX > UB_X) {
Popped.CurrX = 0;
Popped.CurrY++;
}
//最終行を超えた場合
if (Popped.CurrY > UB_Y) continue;
Action<bool> PushSyori = pWillSetCoin =>
{
WillPush.CoinCnt = Popped.CoinCnt;
WillPush.CurrX = Popped.CurrX + 1;
WillPush.CurrY = Popped.CurrY;
WillPush.IsSetCoin = pWillSetCoin;
if (pWillSetCoin) {
//任意の直線上にコインが2枚以上あったらNG
if (HasTwoCoin(Popped.CurrX, Popped.CurrY, WillPush.BanArr))
return;
WillPush.CoinCnt++;
WillPush.BanArr = (char[,])Popped.BanArr.Clone();
WillPush.BanArr[Popped.CurrX, Popped.CurrY] = '*';
}
else WillPush.BanArr = Popped.BanArr;
//対称解の除外で、
//1列目の左のコインの枚数 <= 1列目の右のコインの枚数
if (Popped.CurrY == 0 && UB_X < Popped.CurrX) {
int LeftCnt = 0;
if (WillPush.BanArr[0, 3] == '*') LeftCnt++;
if (WillPush.BanArr[0, 5] == '*') LeftCnt++;
int RightCnt = 0;
if (WillPush.BanArr[0, 7] == '*') RightCnt++;
if (WillPush.BanArr[0, 9] == '*') RightCnt++;
if (LeftCnt > RightCnt) return;
}
stk.Push(WillPush);
};
//コインを置く経路
if (Popped.BanArr[Popped.CurrX, Popped.CurrY] == '-') {
PushSyori(true);
}
//コインを置かない経路
PushSyori(false);
}
PrintAnswer(AnswerCoinCnt, AnswerBanArrList);
}
//任意の直線上にコインが2枚以上あるかを判定
static bool HasTwoCoin(int pCurrX, int pCurrY, char[,] pBanArr)
{
for (int HeniX = -UB_X; HeniX <= UB_X; HeniX++) {
if (pCurrX + HeniX < 0) continue;
if (UB_X < pCurrX + HeniX) break;
for (int HeniY = 0; -UB_Y <= HeniY; HeniY--) {
if (pCurrY + HeniY < 0) break;
//0ベクトルは不可
if (HeniX == 0 && HeniY == 0) continue;
//互いに素でなかったら、Continue
if (HeniX != 0 && HeniY != 0 && DeriveGCD(HeniX, HeniY) != 1)
continue;
if (HasTwoCoinHelper(pCurrX, pCurrY, HeniX, HeniY, pBanArr))
return true;
}
}
return false;
}
//任意の直線上にコインが2枚以上あるか判定
static bool HasTwoCoinHelper(int pCurrX, int pCurrY,
int pHeniX, int pHeniY, char[,] pBanArr)
{
int CoinCnt = 0;
Action<int> wkAct = pKeisuu =>
{
for (int LoopX = pCurrX + pKeisuu * pHeniX,
LoopY = pCurrY + pKeisuu * pHeniY;
0 <= LoopX && LoopX <= UB_X
&& 0 <= LoopY && LoopY <= UB_Y;
LoopX += pKeisuu * pHeniX,
LoopY += pKeisuu * pHeniY) {
if (pBanArr[LoopX, LoopY] == '*')
CoinCnt++;
}
};
wkAct(-1); wkAct(1);
return CoinCnt >= 2;
}
//ユークリッドの互除法で2数の最大公約数を求める
static private int DeriveGCD(int pVal1, int pVal2)
{
pVal1 = Math.Abs(pVal1);
pVal2 = Math.Abs(pVal2);
int WarareruKazu = Math.Max(pVal1, pVal2);
int WaruKazu = Math.Min(pVal1, pVal2);
while (true) {
int Amari = WarareruKazu % WaruKazu;
if (Amari == 0) return WaruKazu;
WarareruKazu = WaruKazu;
WaruKazu = Amari;
}
}
//残りのハイフンの数を求める
static int DeriveRestHyphenCnt(int pCurrX, int pCurrY, char[,] pBanArr)
{
int WillReturn = 0;
for (int X = 0; X <= UB_X; X++) {
for (int Y = pCurrY; Y <= UB_Y; Y++) {
if (pCurrY < Y || pCurrX <= X) {
if (pBanArr[X, Y] == '-') WillReturn++;
}
}
}
return WillReturn;
}
//回転解を除外して、解を表示する
static void PrintAnswer(int pAnswerCoinCnt, List<char[,]> pAnswerBanArrList)
{
for (int I = pAnswerBanArrList.Count - 1; 0 <= I; I--) {
char[,] Kaiten060Do = DeriveKaiten60Do(pAnswerBanArrList[I]);
char[,] Kaiten120Do = DeriveKaiten60Do(Kaiten060Do);
char[,] Kaiten180Do = DeriveKaiten60Do(Kaiten120Do);
char[,] Kaiten240Do = DeriveKaiten60Do(Kaiten180Do);
char[,] Kaiten300Do = DeriveKaiten60Do(Kaiten240Do);
char[,] wkHanten = SayuuHanten(pAnswerBanArrList[I]);
char[,] wkHanten060Do = DeriveKaiten60Do(wkHanten);
char[,] wkHanten120Do = DeriveKaiten60Do(wkHanten060Do);
char[,] wkHanten180Do = DeriveKaiten60Do(wkHanten120Do);
char[,] wkHanten240Do = DeriveKaiten60Do(wkHanten180Do);
char[,] wkHanten300Do = DeriveKaiten60Do(wkHanten240Do);
bool WillRemove = false;
for (int J = 0; J <= I - 1; J++) {
char[,] wkP = pAnswerBanArrList[J];
if (IsSameBan(wkP, Kaiten060Do)) { WillRemove = true; break; }
if (IsSameBan(wkP, Kaiten120Do)) { WillRemove = true; break; }
if (IsSameBan(wkP, Kaiten180Do)) { WillRemove = true; break; }
if (IsSameBan(wkP, Kaiten240Do)) { WillRemove = true; break; }
if (IsSameBan(wkP, Kaiten300Do)) { WillRemove = true; break; }
if (IsSameBan(wkP, wkHanten)) { WillRemove = true; break; }
if (IsSameBan(wkP, wkHanten060Do)) { WillRemove = true; break; }
if (IsSameBan(wkP, wkHanten120Do)) { WillRemove = true; break; }
if (IsSameBan(wkP, wkHanten180Do)) { WillRemove = true; break; }
if (IsSameBan(wkP, wkHanten240Do)) { WillRemove = true; break; }
if (IsSameBan(wkP, wkHanten300Do)) { WillRemove = true; break; }
}
if (WillRemove) pAnswerBanArrList.RemoveAt(I);
}
for (int I = 0; I <= pAnswerBanArrList.Count - 1; I++) {
Console.WriteLine("コインが{0}枚の解{1}", pAnswerCoinCnt, I + 1);
PrintBan(pAnswerBanArrList[I]);
}
Console.WriteLine("経過時間={0}", sw.Elapsed);
}
//左右反転させた盤面を返す
static char[,] SayuuHanten(char[,] pBanArr)
{
char[,] WillReturn = new char[UB_X + 1, UB_Y + 1];
for (int X = 0; X <= UB_X; X++) {
for (int Y = 0; Y <= UB_Y; Y++) {
char wkVal = pBanArr[UB_X - X, Y];
WillReturn[X, Y] = wkVal;
}
}
return WillReturn;
}
//同じ盤面かを判定
static bool IsSameBan(char[,] pArr1, char[,] pArr2)
{
return pArr1.Cast<char>().SequenceEqual(pArr2.Cast<char>());
}
//正六角形を60度回転させた2次元配列を返す
static char[,] DeriveKaiten60Do(char[,] pBanArr)
{
char[,] WillReturn = new char[UB_X + 1, UB_Y + 1];
for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
//'*'と'-'以外をコピー
if (pBanArr[LoopX, LoopY] == '*') continue;
if (pBanArr[LoopX, LoopY] == '-') continue;
WillReturn[LoopX, LoopY] = pBanArr[LoopX, LoopY];
}
}
WillReturn[3, 0] = pBanArr[0, 3];
WillReturn[5, 0] = pBanArr[1, 2];
WillReturn[7, 0] = pBanArr[2, 1];
WillReturn[9, 0] = pBanArr[3, 0];
WillReturn[2, 1] = pBanArr[1, 4];
WillReturn[4, 1] = pBanArr[2, 3];
WillReturn[6, 1] = pBanArr[3, 2];
WillReturn[8, 1] = pBanArr[4, 1];
WillReturn[10, 1] = pBanArr[5, 0];
WillReturn[1, 2] = pBanArr[2, 5];
WillReturn[3, 2] = pBanArr[3, 4];
WillReturn[5, 2] = pBanArr[4, 3];
WillReturn[7, 2] = pBanArr[5, 2];
WillReturn[9, 2] = pBanArr[6, 1];
WillReturn[11, 2] = pBanArr[7, 0];
WillReturn[0, 3] = pBanArr[3, 6];
WillReturn[2, 3] = pBanArr[4, 5];
WillReturn[4, 3] = pBanArr[5, 4];
WillReturn[6, 3] = pBanArr[6, 3];
WillReturn[8, 3] = pBanArr[7, 2];
WillReturn[10, 3] = pBanArr[8, 1];
WillReturn[12, 3] = pBanArr[9, 0];
WillReturn[1, 4] = pBanArr[5, 6];
WillReturn[3, 4] = pBanArr[6, 5];
WillReturn[5, 4] = pBanArr[7, 4];
WillReturn[7, 4] = pBanArr[8, 3];
WillReturn[9, 4] = pBanArr[9, 2];
WillReturn[11, 4] = pBanArr[10, 1];
WillReturn[2, 5] = pBanArr[7, 6];
WillReturn[4, 5] = pBanArr[8, 5];
WillReturn[6, 5] = pBanArr[9, 4];
WillReturn[8, 5] = pBanArr[10, 3];
WillReturn[10, 5] = pBanArr[11, 2];
WillReturn[3, 6] = pBanArr[9, 6];
WillReturn[5, 6] = pBanArr[10, 5];
WillReturn[7, 6] = pBanArr[11, 4];
WillReturn[9, 6] = pBanArr[12, 3];
return WillReturn;
}
//盤面を表示
static void PrintBan(char[,] pBanArr)
{
var sb = new System.Text.StringBuilder();
for (int Y = 0; Y <= UB_Y; Y++) {
for (int X = 0; X <= UB_X; X++) {
char CurrChar = pBanArr[X, Y];
if (CurrChar == 'F') sb.Append(' ');
if (CurrChar == 'S') sb.Append(' ');
if (CurrChar == '-') sb.Append('-');
if (CurrChar == '*') sb.Append('*');
}
sb.AppendLine();
}
Console.WriteLine(sb.ToString());
}
}