using System;
using System.Collections.Generic;
class Program
{
const int UB = 5 - 1;
struct PointDef
{
internal int X;
internal int Y;
}
static void Main()
{
var sw = System.Diagnostics.Stopwatch.StartNew();
int AnswerCnt = 0;
foreach (bool[,] EachMeiroArr in DeriveMeiroArrEnum()) {
PointDef[] VisitedPointArr1 =
DeriveVisitedPointArr(EachMeiroArr,
new PointDef() { X = 0, Y = 0 },
new PointDef() { X = UB, Y = UB },
new PointDef() { X = 0, Y = 1 });
PointDef[] VisitedPointArr2 =
DeriveVisitedPointArr(EachMeiroArr,
new PointDef() { X = UB, Y = UB },
new PointDef() { X = 0, Y = 0 },
new PointDef() { X = 0, Y = -1 });
for (int I = 0; I <= Math.Min(VisitedPointArr1.GetUpperBound(0),
VisitedPointArr2.GetUpperBound(0)); I++) {
if (VisitedPointArr1[I].X == VisitedPointArr2[I].X
&& VisitedPointArr1[I].Y == VisitedPointArr2[I].Y) {
AnswerCnt++;
if (AnswerCnt % 100000 == 0) {
Console.WriteLine("{0}個目の解を発見。経過時間={1}", AnswerCnt, sw.Elapsed);
}
break;
}
if (VisitedPointArr1[I].X == UB && VisitedPointArr1[I].Y == UB)
break;
if (VisitedPointArr2[I].X == 0 && VisitedPointArr2[I].Y == 0)
break;
}
}
Console.WriteLine("解は{0}通り。経過時間={1}", AnswerCnt, sw.Elapsed);
}
struct JyoutaiDefDFS
{
internal int CurrX;
internal int CurrY;
internal bool[,] BanArr;
}
//迷路を列挙
static IEnumerable<bool[,]> DeriveMeiroArrEnum()
{
var stk = new Stack<JyoutaiDefDFS>();
JyoutaiDefDFS WillPush;
//[0,0]に壁は配置できない
WillPush.CurrX = 1;
WillPush.CurrY = 0;
WillPush.BanArr = new bool[UB + 1, UB + 1];
stk.Push(WillPush);
while (stk.Count > 0) {
JyoutaiDefDFS Popped = stk.Pop();
//クリア判定
if (Popped.CurrX == UB && Popped.CurrY == UB) {
yield return Popped.BanArr;
continue;
}
//X座標の繰上げ処理
if (Popped.CurrX > UB) {
Popped.CurrX = 0;
Popped.CurrY++;
}
//壁を配置する経路
WillPush.CurrX = Popped.CurrX + 1;
WillPush.CurrY = Popped.CurrY;
WillPush.BanArr = (bool[,])Popped.BanArr.Clone();
WillPush.BanArr[Popped.CurrX, Popped.CurrY] = true;
//ゴールに到着可能な迷路かを、UnionFindで判定
if (IsValidMeiro(WillPush.BanArr)) {
stk.Push(WillPush);
}
//壁を配置しない経路
WillPush.CurrX = Popped.CurrX + 1;
WillPush.CurrY = Popped.CurrY;
WillPush.BanArr = Popped.BanArr;
stk.Push(WillPush);
}
}
struct JyoutaiDefUnionFind
{
internal int CurrX;
internal int CurrY;
}
//ゴールに到着可能な迷路かを、UnionFindで判定
static bool IsValidMeiro(bool[,] pBanArr)
{
var stk = new Stack<JyoutaiDefUnionFind>();
JyoutaiDefUnionFind WillPush;
WillPush.CurrX = 0;
WillPush.CurrY = 0;
stk.Push(WillPush);
var VisitedSet = new HashSet<string>();
while (stk.Count > 0) {
JyoutaiDefUnionFind Popped = stk.Pop();
//クリア判定
if (VisitedSet.Contains(string.Format("({0},{1})", UB, UB))) {
return true;
}
Action<int, int> PushSyori = (pNewX, pNewY) =>
{
if (pNewX < 0 || UB < pNewX) return;
if (pNewY < 0 || UB < pNewY) return;
//壁には移動不可
if (pBanArr[pNewX, pNewY]) return;
string wkStr = string.Format("({0},{1})", pNewX, pNewY);
if (VisitedSet.Add(wkStr)) {
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 false;
}
//迷路と開始座標と終了座標と変位ベクトルを引数とし、右手法での訪問座標の配列を返す
static PointDef[] DeriveVisitedPointArr(bool[,] pBanArr,
PointDef pStaPos, PointDef pGoalPos, PointDef pHeniVect)
{
var WillReturn = new List<PointDef>();
WillReturn.Add(new PointDef() { X = pStaPos.X, Y = pStaPos.Y });
PointDef CurrPos = pStaPos;
PointDef CurrHeniVect = pHeniVect;
while (true) {
PointDef SakiPos = CurrPos;
SakiPos.X += CurrHeniVect.X;
SakiPos.Y += CurrHeniVect.Y;
//進行先が空なら移動する
if (IsWall(pBanArr, SakiPos) == false) {
CurrPos = SakiPos;
}
else { //進行先が壁の場合
//進行先の左が空の場合、向きを左にして進む
PointDef HidariPos = CurrPos;
PointDef HidariVect = KaitenHidari90Do(CurrHeniVect);
HidariPos.X += HidariVect.X;
HidariPos.Y += HidariVect.Y;
if (IsWall(pBanArr, HidariPos) == false) {
CurrPos = HidariPos;
CurrHeniVect = HidariVect;
}
else { //進行先の左が壁の場合、向きを反転して進む
CurrHeniVect = KaitenHidari90Do(HidariVect);
CurrPos.X += CurrHeniVect.X;
CurrPos.Y += CurrHeniVect.Y;
}
}
//進行方向の右側が空いてたら、変位ベクトルを右に90度回転
PointDef MigiPos = CurrPos;
PointDef MigiVect = KaitenMigi90Do(CurrHeniVect);
MigiPos.X += MigiVect.X;
MigiPos.Y += MigiVect.Y;
if (IsWall(pBanArr, MigiPos) == false) {
CurrHeniVect = MigiVect;
}
WillReturn.Add(new PointDef() { X = CurrPos.X, Y = CurrPos.Y });
if (CurrPos.X == pGoalPos.X && CurrPos.Y == pGoalPos.Y)
break;
}
return WillReturn.ToArray();
}
//右に90度回転させた変位ベクトルを返す
static PointDef KaitenMigi90Do(PointDef pBaseVect)
{
int X = pBaseVect.X;
int Y = pBaseVect.Y;
if (X == 0 && Y == -1) return new PointDef() { X = 1, Y = 0 };
if (X == 0 && Y == 1) return new PointDef() { X = -1, Y = 0 };
if (X == -1 && Y == 0) return new PointDef() { X = 0, Y = -1 };
return new PointDef() { X = 0, Y = 1 };
}
//左に90度回転させた変位ベクトルを返す
static PointDef KaitenHidari90Do(PointDef pBaseVect)
{
int X = pBaseVect.X;
int Y = pBaseVect.Y;
if (X == 0 && Y == -1) return new PointDef() { X = -1, Y = 0 };
if (X == 0 && Y == 1) return new PointDef() { X = 1, Y = 0 };
if (X == -1 && Y == 0) return new PointDef() { X = 0, Y = 1 };
return new PointDef() { X = 0, Y = -1 };
}
//座標を引数として、壁かを判定
static bool IsWall(bool[,] pBanArr, PointDef pTargetPoint)
{
int X = pTargetPoint.X;
int Y = pTargetPoint.Y;
if (X < 0 || pBanArr.GetUpperBound(0) < X) return true;
if (Y < 0 || pBanArr.GetUpperBound(1) < Y) return true;
return pBanArr[X, Y];
}
}