using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static int UB_X;
const int UB_Y = 4 - 1;
static System.Diagnostics.Stopwatch sw = System.Diagnostics.Stopwatch.StartNew();
static void Main()
{
UB_X = 4 - 1; Solve();
UB_X = 6 - 1; Solve();
}
struct JyoutaiDef
{
internal char[,] BanArr;
internal int Level;
}
static void Solve()
{
var Queue = new Queue<JyoutaiDef>();
JyoutaiDef WillEnque;
var VisitedSet = new HashSet<uint>();
List<char[,]> InitList;
if (UB_X == 4 - 1) InitList = DeriveInitList_4_4();
else InitList = DeriveInitList_6_4();
foreach (char[,] EachInitList in InitList) {
WillEnque.BanArr = EachInitList;
WillEnque.Level = 0;
Queue.Enqueue(WillEnque);
VisitedSet.Add(BanToUntSet(EachInitList).First());
}
int AnswerLevel = 0;
List<char[,]> AnswerBanArrList = new List<char[,]>();
while (Queue.Count > 0) {
JyoutaiDef Dequeued = Queue.Dequeue();
if (AnswerLevel < Dequeued.Level) {
AnswerBanArrList.Clear();
AnswerLevel = Dequeued.Level;
Console.WriteLine("移動回数{0,2}の解候補を発見。経過時間={1}",
AnswerLevel, sw.Elapsed);
}
AnswerBanArrList.Add(Dequeued.BanArr);
//青に隣接した白の座標の、ペアのListを返す
List<RinsetuInfoDef> RinsetuInfoList = DeriveRinsetuInfoList(Dequeued.BanArr);
foreach (RinsetuInfoDef EachRinsetuInfo in RinsetuInfoList) {
WillEnque.BanArr = (char[,])Dequeued.BanArr.Clone();
WillEnque.BanArr[EachRinsetuInfo.BX, EachRinsetuInfo.BY] = 'W';
WillEnque.BanArr[EachRinsetuInfo.WX, EachRinsetuInfo.WY] = 'B';
//メモ化探索
HashSet<uint> wkHashSet = BanToUntSet(WillEnque.BanArr);
if (VisitedSet.Overlaps(wkHashSet)) continue;
VisitedSet.Add(wkHashSet.First());
WillEnque.Level = Dequeued.Level + 1;
Queue.Enqueue(WillEnque);
}
}
HashSet<uint> AnswerSet = new HashSet<uint>();
AnswerBanArrList.ForEach(X => AnswerSet.UnionWith(BanToUntSet(X)));
Console.WriteLine("解は、移動回数{0}で{1,2}通り。経過時間={2}",
AnswerLevel, AnswerSet.Count, sw.Elapsed);
Console.WriteLine("解の例");
PrintBan(AnswerBanArrList[0]);
}
//最初の盤面のListを返す(4*4の盤面用)
static List<char[,]> DeriveInitList_4_4()
{
var WillReturn = new List<char[,]>();
WillReturn.Add(ConvCharArr(new string[]{"BBWW",
"BBWW",
"BBWW",
"BBWW"}));
return WillReturn;
}
//最初の盤面のListを返す(6*4の盤面用)
static List<char[,]> DeriveInitList_6_4()
{
var WillReturn = new List<char[,]>();
WillReturn.Add(ConvCharArr(new string[]{"BBBWWW",
"BBBWWW",
"BBBWWW",
"BBBWWW"}));
WillReturn.Add(ConvCharArr(new string[]{"BBBBBB",
"BBBBBB",
"WWWWWW",
"WWWWWW"}));
return WillReturn;
}
//String型の配列を、Char型の2次元配列に変換
static char[,] ConvCharArr(string[] pStrArr)
{
char[,] WillReturn = new char[UB_X + 1, UB_Y + 1];
for (int Y = 0; Y <= pStrArr.GetUpperBound(0); Y++) {
for (int X = 0; X <= pStrArr[Y].Length - 1; X++) {
WillReturn[X, Y] = pStrArr[Y][X];
}
}
return WillReturn;
}
struct RinsetuInfoDef
{
internal int BX;
internal int BY;
internal int WX;
internal int WY;
}
//青に隣接した白の座標の、ペアのListを返す
static List<RinsetuInfoDef> DeriveRinsetuInfoList(char[,] pBanArr)
{
var WillReturn = new List<RinsetuInfoDef>();
//座標を引数として、Wかを返す
Func<int, int, bool> wkFunc = (pX, pY) =>
{
if (pX < 0 || UB_X < pX) return false;
if (pY < 0 || UB_Y < pY) return false;
return pBanArr[pX, pY] == 'W';
};
for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
if (pBanArr[LoopX, LoopY] != 'B') continue;
if (wkFunc(LoopX, LoopY - 1)) {
WillReturn.Add(
new RinsetuInfoDef() { BX = LoopX, BY = LoopY, WX = LoopX, WY = LoopY - 1 });
}
if (wkFunc(LoopX, LoopY + 1)) {
WillReturn.Add(
new RinsetuInfoDef() { BX = LoopX, BY = LoopY, WX = LoopX, WY = LoopY + 1 });
}
if (wkFunc(LoopX - 1, LoopY)) {
WillReturn.Add(
new RinsetuInfoDef() { BX = LoopX, BY = LoopY, WX = LoopX - 1, WY = LoopY });
}
if (wkFunc(LoopX + 1, LoopY)) {
WillReturn.Add(
new RinsetuInfoDef() { BX = LoopX, BY = LoopY, WX = LoopX + 1, WY = LoopY });
}
}
}
return WillReturn;
}
//盤面をUInt型のSetに変換
static HashSet<uint> BanToUntSet(char[,] pBanArr)
{
var WillReturn = new HashSet<uint>();
var sbList = new List<System.Text.StringBuilder>();
for (int I = 1; I <= (UB_X == UB_Y ? 8 : 4); I++)
sbList.Add(new System.Text.StringBuilder());
for (int X = 0; X <= UB_X; X++) {
for (int Y = 0; Y <= UB_Y; Y++) {
Func<char, char> wkFunc = pChar => pChar == 'B' ? '0' : '1';
sbList[0].Append(wkFunc(pBanArr[X, Y]));
sbList[1].Append(wkFunc(pBanArr[X, UB_Y - Y]));
sbList[2].Append(wkFunc(pBanArr[UB_X - X, Y]));
sbList[3].Append(wkFunc(pBanArr[UB_X - X, UB_Y - Y]));
if (UB_X == UB_Y) {
sbList[4].Append(wkFunc(pBanArr[Y, X]));
sbList[5].Append(wkFunc(pBanArr[UB_Y - Y, X]));
sbList[6].Append(wkFunc(pBanArr[Y, UB_X - X]));
sbList[7].Append(wkFunc(pBanArr[UB_Y - Y, UB_X - X]));
}
}
}
sbList.ForEach(X => WillReturn.Add(Convert.ToUInt32(X.ToString(), 2)));
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++) {
sb.Append(pBanArr[X, Y]);
}
sb.AppendLine();
}
Console.WriteLine(sb.ToString());
}
}