using System;
using System.Collections.Generic;
class Program
{
const int UB = 8 - 1;
struct JyoutaiDef
{
internal int Level;
internal char[,] BanArr;
internal List<char[,]> BanArrLogList;
}
static void Main()
{
var sw = System.Diagnostics.Stopwatch.StartNew();
//反復深化深さ優先探索で解く
for (int Depth = 1; Depth <= 8 * 8 - 4; Depth++) {
Console.WriteLine("深さ制限={0}で解を検証中。経過時間={1}", Depth, sw.Elapsed);
List<Char[,]> AnswerBanArrLog = ExecDFS(Depth);
if (AnswerBanArrLog.Count == 0) continue;
for (int I = 0; I <= AnswerBanArrLog.Count - 1; I++) {
Console.WriteLine("{0}手目", I);
PrintBan(AnswerBanArrLog[I]);
}
break;
}
}
//深さ制限を引数として深さ優先探索を行う
static List<Char[,]> ExecDFS(int pDepthMax)
{
var WillReturnCharArrList = new List<char[,]>();
var stk = new Stack<JyoutaiDef>();
JyoutaiDef WillPush;
WillPush.Level = 0;
WillPush.BanArr = new char[UB + 1, UB + 1];
for (int Y = 0; Y <= UB; Y++) {
for (int X = 0; X <= UB; X++) {
WillPush.BanArr[X, Y] = '□';
}
}
WillPush.BanArr[3, 3] = WillPush.BanArr[4, 4] = '○';
WillPush.BanArr[3, 4] = WillPush.BanArr[4, 3] = '●';
WillPush.BanArrLogList = new List<char[,]>() { WillPush.BanArr };
stk.Push(WillPush);
while (stk.Count > 0) {
JyoutaiDef Popped = stk.Pop();
//クリア判定
if (IsClear(Popped.BanArr))
return Popped.BanArrLogList;
//レベル制限
if (pDepthMax < Popped.Level) continue;
//石を配置した盤面を返す
List<Char[,]> BanList = SetStone(Popped.Level, Popped.BanArr);
WillPush.Level = Popped.Level + 1;
//オセロの初手は回転させると同じなので、1手に限定する
if (WillPush.Level == 1) BanList.RemoveRange(0, BanList.Count - 1);
//パスの場合
if (BanList.Count == 0) {
WillPush.BanArr = Popped.BanArr;
WillPush.BanArrLogList = new List<char[,]>(Popped.BanArrLogList);
WillPush.BanArrLogList.Add(WillPush.BanArr);
stk.Push(WillPush);
}
else {
BanList.ForEach(X =>
{
WillPush.BanArr = X;
WillPush.BanArrLogList = new List<char[,]>(Popped.BanArrLogList);
WillPush.BanArrLogList.Add(X);
stk.Push(WillPush);
});
}
}
return WillReturnCharArrList;
}
//クリア判定
static bool IsClear(char[,] pBanArr)
{
bool HasBlack = false;
bool HasWhite = false;
for (int Y = 0; Y <= UB; Y++) {
for (int X = 0; X <= UB; X++) {
if (pBanArr[X, Y] == '●') HasBlack = true;
if (pBanArr[X, Y] == '○') HasWhite = true;
}
}
return (HasBlack && HasWhite) == false;
}
//石を配置した盤面を返す
static List<Char[,]> SetStone(int pLevel, char[,] pBanArr)
{
var WillReturnCharArrList = new List<char[,]>();
//手番を求める
bool IsKuroban = pLevel % 2 == 0;
//配置候補の座標を求める
for (int Y = 0; Y <= UB; Y++) {
for (int X = 0; X <= UB; X++) {
if (pBanArr[X, Y] != '□') continue;
char[,] wkBanArr = (char[,])pBanArr.Clone();
wkBanArr[X, Y] = IsKuroban ? '●' : '○';
bool CanSet = false;
CanSet |= ReverseStone(wkBanArr, X, Y, 0, -1);
CanSet |= ReverseStone(wkBanArr, X, Y, 1, -1);
CanSet |= ReverseStone(wkBanArr, X, Y, 1, 0);
CanSet |= ReverseStone(wkBanArr, X, Y, 1, 1);
CanSet |= ReverseStone(wkBanArr, X, Y, 0, 1);
CanSet |= ReverseStone(wkBanArr, X, Y, -1, 1);
CanSet |= ReverseStone(wkBanArr, X, Y, -1, 0);
CanSet |= ReverseStone(wkBanArr, X, Y, -1, -1);
if (CanSet == false) continue;
WillReturnCharArrList.Add(wkBanArr);
}
}
return WillReturnCharArrList;
}
//盤面と石を置いた座標とチェック方向を引数とし、
//裏返せる石があれば裏返し、1枚でも裏返したらTrueを返す
static bool ReverseStone(char[,] pBanArr, int pSetX, int pSetY, int pHoukouX, int pHoukouY)
{
char SetStone = pBanArr[pSetX, pSetY];
char ReverseStone = SetStone == '●' ? '○' : '●';
bool CanReverse = false;
//裏返し可能かを判定
for (int I = 1; I <= 7; I++) {
int X = pSetX + pHoukouX * I;
int Y = pSetY + pHoukouY * I;
if (X < 0 || UB < X) return false;
if (Y < 0 || UB < Y) return false;
if (I == 1 && pBanArr[X, Y] != ReverseStone) return false;
if (I >= 2 && pBanArr[X, Y] == '□') return false;
if (I >= 2 && pBanArr[X, Y] == SetStone) {
CanReverse = true;
break;
}
}
//裏返し処理
if (CanReverse) {
for (int I = 1; I <= 7; I++) {
int X = pSetX + pHoukouX * I;
int Y = pSetY + pHoukouY * I;
if (pBanArr[X, Y] == SetStone) break;
pBanArr[X, Y] = SetStone;
}
return true;
}
return false;
}
//盤面を表示
static void PrintBan(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();
}
Console.WriteLine(sb.ToString());
}
}
