using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static int UB_X;
static int UB_Y;
static int mQuestionNo;
static void Main()
{
var sw = System.Diagnostics.Stopwatch.StartNew();
mQuestionNo = 1;
Solve(new string[]{"Ａ・・・",
"・・ＢＡ",
"ＣＢ・Ｃ",
"・・・・"});
mQuestionNo = 2;
Solve(new string[]{"・・・Ａ・・・・",
"・Ｂ・・・・Ｃ・",
"・・・・・・・・",
"・Ｃ・・・・・Ｅ",
"・・・Ｄ・・・・",
"Ｅ・・・・・Ｂ・",
"・・Ａ・・・・・",
"・・・・・・・Ｄ"});
Console.WriteLine("経過時間={0}", sw.Elapsed);
}
static void Solve(string[] pStrArr)
{
Console.WriteLine("{0}問目を解きます。", mQuestionNo);
UB_X = pStrArr[0].Length - 1;
UB_Y = pStrArr.Length - 1;
char[,] wkStaBanArr = new char[UB_X + 1, UB_Y + 1];
for (int X = 0; X <= UB_X; X++) {
for (int Y = 0; Y <= UB_Y; Y++) {
wkStaBanArr[X, Y] = pStrArr[Y][X];
}
}
//リンクの開始座標と終了座標を取得
DeriveLinkInfoArr(wkStaBanArr);
var PrevBanArrList = new List<char[,]>() { wkStaBanArr };
foreach (LinkInfoDef EachLinkInfo in mLinkInfoArr) {
var CurrBanArrList = new List<char[,]>();
PrevBanArrList.ForEach(X => CurrBanArrList.AddRange(ExecDFS(X, EachLinkInfo)));
PrevBanArrList = CurrBanArrList;
}
for (int I = 0; I <= PrevBanArrList.Count - 1; I++) {
Console.WriteLine("解{0}", I + 1);
PrintBan(PrevBanArrList[I]);
}
}
struct JyoutaiDefDFS
{
internal int CurrX;
internal int CurrY;
internal char[,] BanArr;
}
//深さ優先探索でリンクを作成
static List<char[,]> ExecDFS(char[,] pBanArr, LinkInfoDef pLinkInfo)
{
var WillReturn = new List<char[,]>();
var Stk = new Stack<JyoutaiDefDFS>();
JyoutaiDefDFS WillPush;
WillPush.CurrX = pLinkInfo.StaX;
WillPush.CurrY = pLinkInfo.StaY;
WillPush.BanArr = pBanArr;
Stk.Push(WillPush);
while (Stk.Count > 0) {
JyoutaiDefDFS Popped = Stk.Pop();
//クリア判定
if (Popped.CurrX == pLinkInfo.EndX && Popped.CurrY == pLinkInfo.EndY) {
WillReturn.Add(Popped.BanArr);
continue;
}
Action<int, int> PushSyori = (pNewX, pNewY) =>
{
if (pNewX < 0 || UB_X < pNewX) return;
if (pNewY < 0 || UB_Y < pNewY) return;
bool wkIsEnd = (pNewX == pLinkInfo.EndX && pNewY == pLinkInfo.EndY);
if (wkIsEnd == false && Popped.BanArr[pNewX, pNewY] != '・') return;
WillPush.CurrX = pNewX;
WillPush.CurrY = pNewY;
WillPush.BanArr = (char[,])Popped.BanArr.Clone();
WillPush.BanArr[pNewX, pNewY] = pLinkInfo.ID;
//特殊枝切り BとCとDとEのリンクチェック
if (mQuestionNo == 2 && pLinkInfo.ID == 'Ａ') {
for (int X = 2; X <= 5; X++) {
int SpaceCnt = 0;
for (int Y = 0; Y <= UB_Y; Y++) {
if (WillPush.BanArr[X, Y] == '・')
SpaceCnt++;
}
if (X == 2 && SpaceCnt < 3) return;
if (X == 3 && SpaceCnt < 3) return;
if (X == 4 && SpaceCnt < 4) return;
if (X == 5 && SpaceCnt < 5) return;
}
}
//ゴールに到達不能なら枝切り
Func<int, int, bool> wkFunc = (pX, pY) =>
{
if (pX < 0 || UB_X < pX) return false;
if (pY < 0 || UB_Y < pY) return false;
//その座標に存在する場合は可
if (pX == WillPush.CurrX && pY == WillPush.CurrY)
return true;
return WillPush.BanArr[pX, pY] == '・';
};
if (wkIsEnd == false) {
bool IsOK = false;
//ゴールにいる場合は可
if (WillPush.CurrX == pLinkInfo.EndX && WillPush.CurrY == pLinkInfo.EndY)
IsOK = true;
if (wkFunc(pLinkInfo.EndX, pLinkInfo.EndY - 1)) IsOK = true;
if (wkFunc(pLinkInfo.EndX, pLinkInfo.EndY + 1)) IsOK = true;
if (wkFunc(pLinkInfo.EndX - 1, pLinkInfo.EndY)) IsOK = true;
if (wkFunc(pLinkInfo.EndX + 1, pLinkInfo.EndY)) IsOK = true;
if (IsOK == false) return;
}
//UnionFindで枝切り判定
if (WillEdakiri(WillPush.BanArr, pLinkInfo.ID)) return;
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 WillReturn;
}
//UnionFindで枝切り判定
static bool WillEdakiri(char[,] pBanArr, char pID)
{
foreach (LinkInfoDef EachLinkInfo in mLinkInfoArr) {
if (pID.CompareTo(EachLinkInfo.ID) >= 0) continue;
if (ExecUnionFind(pBanArr, EachLinkInfo) == false)
return true;
}
return false;
}
struct JyoutaiDefUnionFind
{
internal int CurrX;
internal int CurrY;
}
//UnionFindでリンクを作成可能かを返す
static bool ExecUnionFind(char[,] pBanArr, LinkInfoDef pLinkInfo)
{
var Stk = new Stack<JyoutaiDefUnionFind>();
JyoutaiDefUnionFind WillPush;
WillPush.CurrX = pLinkInfo.StaX;
WillPush.CurrY = pLinkInfo.StaY;
Stk.Push(WillPush);
var VisitedSet = new HashSet<string>();
while (Stk.Count > 0) {
JyoutaiDefUnionFind Popped = Stk.Pop();
//クリア判定
if (Popped.CurrX == pLinkInfo.EndX && Popped.CurrY == pLinkInfo.EndY)
return true;
Action<int, int> PushSyori = (pNewX, pNewY) =>
{
if (pNewX < 0 || UB_X < pNewX) return;
if (pNewY < 0 || UB_Y < pNewY) return;
bool wkIsEnd = (pNewX == pLinkInfo.EndX && pNewY == pLinkInfo.EndY);
if (wkIsEnd == false && pBanArr[pNewX, pNewY] != '・') return;
if (VisitedSet.Add(string.Format("({0},{1})", pNewX, pNewY))) {
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;
}
struct LinkInfoDef
{
internal char ID;
internal int StaX;
internal int StaY;
internal int EndX;
internal int EndY;
}
static LinkInfoDef[] mLinkInfoArr;
//リンクの開始座標と終了座標を取得
static void DeriveLinkInfoArr(char[,] pBanArr)
{
var LinkInfoList = new List<LinkInfoDef>();
char[] IDArr = pBanArr.Cast<char>().Where(A => A != '・').Distinct().ToArray();
Array.Sort(IDArr);
LinkInfoDef WillAdd;
foreach (char EachID in IDArr) {
WillAdd.ID = EachID;
WillAdd.StaX = WillAdd.StaY = -1;
WillAdd.EndX = WillAdd.EndY = -1;
int HitCnt = 0;
for (int Y = 0; Y <= UB_Y; Y++) {
for (int X = 0; X <= UB_X; X++) {
if (pBanArr[X, Y] != EachID) continue;
HitCnt++;
if (HitCnt == 1) {
WillAdd.StaX = X; WillAdd.StaY = Y;
}
if (HitCnt == 2) {
WillAdd.EndX = X; WillAdd.EndY = Y;
LinkInfoList.Add(WillAdd);
}
}
}
}
mLinkInfoArr = LinkInfoList.ToArray();
}
//盤面を出力
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());
}
}