using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
struct PointDef
{
internal int X;
internal int Y;
}
//数値情報の構造体
struct NumInfoDef
{
internal PointDef Point; //数値の座標
internal LinkInfoDef[] LinkInfoArr; //リンク情報の配列
}
static NumInfoDef[] mNumInfoArr; //数値情報の配列
//リンク情報の構造体
struct LinkInfoDef
{
internal PointDef StaPos; //始点の座標
internal PointDef EndPos; //終点の座標
internal int HeniX; //変位ベクトルのX成分
internal int HeniY; //変位ベクトルのY成分
}
static char[,] mQuestionArr;
static int mNodeCnt;
static int UB_X;
static int UB_Y;
//問題を定義
static void QuestionDef()
{
string[] Q01Arr ={"４□４□□２□□３",
"□□□□□□□□□",
"６□８□４□□１□",
"□□□□□□１□３",
"□□２□２□□１□",
"４□□３□２□□□",
"□□□□□□２□３",
"□１□５□４□□□",
"３□３□２□３□２"};
string[] wkArr = Q01Arr;
UB_X = wkArr[0].Length - 1;
UB_Y = wkArr.GetUpperBound(0);
//半角文字で盤面を保持
mQuestionArr = 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 CurrChar = wkArr[Y][X];
if (CurrChar == '□') mQuestionArr[X, Y] = ' ';
else {
mQuestionArr[X, Y] = (char)('0' + CurrChar - '０');
mNodeCnt++;
}
}
}
}
static void Main()
{
//問題を定義
QuestionDef();
//第1フェーズ 数値情報を作成する
CreateNumInfoArr();
//デバッグ用の数値情報を出力
//DebugPrintNumInfo();
char[,] wkBanArr = (char[,])mQuestionArr.Clone();
//第2フェーズ 確定探索
ExecKakuteiTansaku(wkBanArr);
//第3フェーズ 確定探索付の深さ優先探索
ExecDFS(wkBanArr);
}
//第1フェーズ 数値情報を作成する
static void CreateNumInfoArr()
{
var NumInfoList = new List<NumInfoDef>();
for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
//数値マスでない場合
if (mQuestionArr[LoopX, LoopY] == ' ') continue;
NumInfoDef wkNumInfo;
PointDef CurrPoint = new PointDef() { X = LoopX, Y = LoopY };
wkNumInfo.Point = CurrPoint;
wkNumInfo.LinkInfoArr = DeriveLinkInfoArr(CurrPoint);
NumInfoList.Add(wkNumInfo);
}
}
mNumInfoArr = NumInfoList.ToArray();
}
//数値マスの座標を引数として、リンク情報の配列を返す
static LinkInfoDef[] DeriveLinkInfoArr(PointDef pNumPos)
{
var LinkInfoList = new List<LinkInfoDef>();
Action<int, int> AddAct = (pHeniX, pHeniY) =>
{
LinkInfoDef wkLinkInfo;
int LoopX = pNumPos.X, LoopY = pNumPos.Y;
LoopX += pHeniX; LoopY += pHeniY;
wkLinkInfo.StaPos = new PointDef() { X = LoopX, Y = LoopY };
wkLinkInfo.HeniX = pHeniX;
wkLinkInfo.HeniY = pHeniY;
while (true) {
//範囲外の場合
if (LoopX < 0 || UB_X < LoopX) break;
if (LoopY < 0 || UB_Y < LoopY) break;
//リンクを貼れる場合
if ('1' <= mQuestionArr[LoopX, LoopY]
&& mQuestionArr[LoopX, LoopY] <= '8') {
wkLinkInfo.EndPos = new PointDef() { X = LoopX, Y = LoopY };
LinkInfoList.Add(wkLinkInfo);
break;
}
LoopX += pHeniX; LoopY += pHeniY;
}
};
AddAct(0, -1); AddAct(0, 1);
AddAct(-1, 0); AddAct(1, 0);
return LinkInfoList.ToArray();
}
//デバッグ用の数値情報を出力
static void DebugPrintNumInfo()
{
for (int I = 0; I <= mNumInfoArr.GetUpperBound(0); I++) {
Console.WriteLine("■■■■■■■■■■■■■");
Console.WriteLine("{0}個目の数値情報", I + 1);
Console.WriteLine("Point=({0},{1})", mNumInfoArr[I].Point.X, mNumInfoArr[I].Point.Y);
Console.WriteLine("リンク情報の配列 ");
foreach (LinkInfoDef EachLinkInfo in mNumInfoArr[I].LinkInfoArr) {
Console.WriteLine("始点({0},{1}),終点({2},{3})",
EachLinkInfo.StaPos.X, EachLinkInfo.StaPos.Y,
EachLinkInfo.EndPos.X, EachLinkInfo.EndPos.Y);
}
Console.WriteLine();
}
}
//第2フェーズ 確定探索を行い有効な盤面かを返す
static bool ExecKakuteiTansaku(char[,] pBanArr)
{
while (true) {
char[,] PrevBanArr = (char[,])pBanArr.Clone();
//確定探索1 ノード間のリンクを貼れることが確定する場合
if (KakuteiTansaku1(pBanArr) == false) return false;
//確定探索で確定するマスがなくなったらBreak
if (pBanArr.Cast<char>().SequenceEqual(PrevBanArr.Cast<char>())) break;
}
return true;
}
//確定探索1 ノード間のリンクを貼れることが確定する場合
//戻り値として、有効な盤面かを返す
static bool KakuteiTansaku1(char[,] pBanArr)
{
for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
bool WillContinue = true;
if ('1' <= pBanArr[LoopX, LoopY] && pBanArr[LoopX, LoopY] <= '8')
WillContinue = false;
if (WillContinue) continue;
//数値の座標を引数として、設置できるリンクのListを返す
PointDef CurrPoint = new PointDef() { X = LoopX, Y = LoopY };
int StaRestCnt = pBanArr[LoopX, LoopY] - '0';
List<CanSetLinkInfoDef> CanSetLinkList =
DeriveCanSetLinkList(pBanArr, StaRestCnt, CurrPoint);
//閉路ができるリンクをRemove
HeiroRemove(pBanArr, CanSetLinkList, StaRestCnt, CurrPoint);
//橋の数の昇順にソートしておく
CanSetLinkList.Sort((A, B) => A.LinkCnt.CompareTo(B.LinkCnt));
//座標ごとの最大値を求めておく
var MaxDict = new Dictionary<string, int>();
foreach (CanSetLinkInfoDef EachCanSetLink in CanSetLinkList) {
PointDef EndPos = EachCanSetLink.LinkInfo.EndPos;
string CurrKey = GetHash(EndPos);
int CurrVal;
if (MaxDict.TryGetValue(CurrKey, out CurrVal)) {
if (CurrVal < EachCanSetLink.LinkCnt)
MaxDict[CurrKey] = EachCanSetLink.LinkCnt;
}
else MaxDict[CurrKey] = EachCanSetLink.LinkCnt;
}
int MaxSum = MaxDict.Values.Sum();
//リンクを引かなければ、解なしになる場合は、リンクを貼る
//橋の数でソート済なので、1本、2本の順序で調べる
foreach (CanSetLinkInfoDef EachCanSetLink in CanSetLinkList) {
int JyogaiVal = MaxDict[GetHash(EachCanSetLink.LinkInfo.EndPos)];
if (StaRestCnt > MaxSum - JyogaiVal) {
SetHashi(pBanArr, EachCanSetLink);
return true;
}
}
if (CanSetLinkList.Count == 0) return false;
if (CanSetLinkList.Count == 1) {
SetHashi(pBanArr, CanSetLinkList[0]);
}
}
}
return true;
}
//設置できるリンク情報の構造体
struct CanSetLinkInfoDef
{
internal LinkInfoDef LinkInfo;
internal int LinkCnt;
}
//数値の座標を引数として、設置できるリンクのListを返す
static List<CanSetLinkInfoDef> DeriveCanSetLinkList(char[,] pBanArr, int pStaRestCnt, PointDef pPoint)
{
var WillReturn = new List<CanSetLinkInfoDef>();
int CurrX = pPoint.X;
int CurrY = pPoint.Y;
int wkInd = Array.FindIndex(mNumInfoArr, A => A.Point.X == CurrX && A.Point.Y == CurrY);
NumInfoDef CurrNumInfo = mNumInfoArr[wkInd];
foreach (LinkInfoDef EachLinkInfo in CurrNumInfo.LinkInfoArr) {
WillReturn.AddRange(DeriveCanSetLinkListHelper(pBanArr, pStaRestCnt, EachLinkInfo));
}
return WillReturn;
}
//リンク情報を引数として、設置できるリンク情報のListを返す
static List<CanSetLinkInfoDef> DeriveCanSetLinkListHelper(
char[,] pBanArr, int pStaRestCnt, LinkInfoDef pLinkInfo)
{
var WillReturn = new List<CanSetLinkInfoDef>();
//既に別の橋が引かれていたら引けない
var NGList = new List<char>();
//横のリンクなら、縦の橋があってはいけない
if (Math.Abs(pLinkInfo.HeniX) > 0) NGList.AddRange(new char[] { 'C', 'D' });
//縦のリンクなら、横の橋があってはいけない
if (Math.Abs(pLinkInfo.HeniY) > 0) NGList.AddRange(new char[] { 'A', 'B' });
int CurrX = pLinkInfo.StaPos.X;
int CurrY = pLinkInfo.StaPos.Y;
while (true) {
if (NGList.IndexOf(pBanArr[CurrX, CurrY]) >= 0) {
return WillReturn;
}
CurrX += pLinkInfo.HeniX;
CurrY += pLinkInfo.HeniY;
if (CurrX == pLinkInfo.EndPos.X && CurrY == pLinkInfo.EndPos.Y)
break;
}
//既に引かれている橋の数
int KizonCnt = 0;
int StaX = pLinkInfo.StaPos.X;
int StaY = pLinkInfo.StaPos.Y;
char StaMasu = pBanArr[StaX, StaY];
if (StaMasu == 'A' || StaMasu == 'C') KizonCnt = 1;
if (StaMasu == 'B' || StaMasu == 'D') KizonCnt = 2;
if (KizonCnt == 2) return WillReturn;
//終点ノードへの残りの橋の数
int EndRestCnt = pBanArr[pLinkInfo.EndPos.X, pLinkInfo.EndPos.Y] - '0';
if (EndRestCnt == 0) return WillReturn;
//橋を2本引ける場合
if (KizonCnt == 0 && pStaRestCnt >= 2 && EndRestCnt >= 2) {
CanSetLinkInfoDef WillAdd;
WillAdd.LinkInfo = pLinkInfo;
WillAdd.LinkCnt = 2;
WillReturn.Add(WillAdd);
}
//橋を1本引ける場合
if (pStaRestCnt >= 1 && EndRestCnt >= 1) {
CanSetLinkInfoDef WillAdd;
WillAdd.LinkInfo = pLinkInfo;
WillAdd.LinkCnt = 1;
WillReturn.Add(WillAdd);
}
return WillReturn;
}
//閉路ができるリンクをRemove
static void HeiroRemove(char[,] pBanArr, List<CanSetLinkInfoDef> pCanSetLinkList,
int pStaRestCnt, PointDef pCurrPoint)
{
for (int I = pCanSetLinkList.Count - 1; 0 <= I; I--) {
if (pStaRestCnt - pCanSetLinkList[I].LinkCnt > 0) continue;
char[,] CheckBanArr = (char[,])pBanArr.Clone();
SetHashi(CheckBanArr, pCanSetLinkList[I]);
int ZeroNodeCnt;
bool IsRenketuNonZeroNode;
DeriveZeroNodeShima(CheckBanArr, pCurrPoint,
out ZeroNodeCnt, out IsRenketuNonZeroNode);
if (ZeroNodeCnt < mNodeCnt && IsRenketuNonZeroNode == false)
pCanSetLinkList.RemoveAt(I);
}
}
//設置するリンク情報を引数として、橋を設置
static void SetHashi(char[,] pBanArr, CanSetLinkInfoDef pCanSetLinkInfo)
{
int StaX = pCanSetLinkInfo.LinkInfo.StaPos.X;
int StaY = pCanSetLinkInfo.LinkInfo.StaPos.Y;
int EndX = pCanSetLinkInfo.LinkInfo.EndPos.X;
int EndY = pCanSetLinkInfo.LinkInfo.EndPos.Y;
int HeniX = pCanSetLinkInfo.LinkInfo.HeniX;
int HeniY = pCanSetLinkInfo.LinkInfo.HeniY;
int LinkCnt = pCanSetLinkInfo.LinkCnt;
char SetChar = '\0';
bool IsYokoLink = Math.Abs(HeniX) > 0;
if (LinkCnt == 1 && IsYokoLink) {
if (pBanArr[StaX, StaY] == ' ') SetChar = 'A';
if (pBanArr[StaX, StaY] == 'A') SetChar = 'B';
}
if (LinkCnt == 1 && IsYokoLink == false) {
if (pBanArr[StaX, StaY] == ' ') SetChar = 'C';
if (pBanArr[StaX, StaY] == 'C') SetChar = 'D';
}
if (LinkCnt == 2 && IsYokoLink) SetChar = 'B';
if (LinkCnt == 2 && IsYokoLink == false) SetChar = 'D';
int LoopX = StaX;
int LoopY = StaY;
while (true) {
pBanArr[LoopX, LoopY] = SetChar;
LoopX += HeniX;
LoopY += HeniY;
if (LoopX == EndX && LoopY == EndY) break;
}
//残りの橋の数をデクリメント
int wkX = StaX - HeniX;
int wkY = StaY - HeniY;
for (int I = 1; I <= LinkCnt; I++) {
pBanArr[wkX, wkY]--;
pBanArr[EndX, EndY]--;
}
}
struct JyoutaiDefUnionFind
{
internal int CurrX;
internal int CurrY;
}
//0のノードの座標を引数として、連結した0ノードの数と、0以外のノードと連結しているかを返す
static void DeriveZeroNodeShima(char[,] pBanArr, PointDef pZeroNodePos,
out int pZeroNodeCnt, out bool pIsRenketuNonZeroNode)
{
pZeroNodeCnt = 0;
pIsRenketuNonZeroNode = false;
var VisitedSet = new HashSet<string>();
VisitedSet.Add(GetHash(pZeroNodePos));
var Stk = new Stack<JyoutaiDefUnionFind>();
JyoutaiDefUnionFind WillPush;
WillPush.CurrX = pZeroNodePos.X;
WillPush.CurrY = pZeroNodePos.Y;
Stk.Push(WillPush);
while (Stk.Count > 0) {
JyoutaiDefUnionFind Popped = Stk.Pop();
int CurrX = Popped.CurrX;
int CurrY = Popped.CurrY;
//0以外のノードと連結していたら終了
if ('0' < pBanArr[CurrX, CurrY]) {
pIsRenketuNonZeroNode = true;
return;
}
pZeroNodeCnt++;
int wkInd = Array.FindIndex(mNumInfoArr, A => A.Point.X == CurrX && A.Point.Y == CurrY);
foreach (LinkInfoDef EachLinkInfo in mNumInfoArr[wkInd].LinkInfoArr) {
int StaX = EachLinkInfo.StaPos.X;
int StaY = EachLinkInfo.StaPos.Y;
int EndX = EachLinkInfo.EndPos.X;
int EndY = EachLinkInfo.EndPos.Y;
bool IsYokoLink = Math.Abs(EachLinkInfo.HeniX) > 0;
if (IsYokoLink) {
if (pBanArr[StaX, StaY] != 'A' && pBanArr[StaX, StaY] != 'B')
continue;
}
else {
if (pBanArr[StaX, StaY] != 'C' && pBanArr[StaX, StaY] != 'D')
continue;
}
//再訪禁止
if (VisitedSet.Add(GetHash(EndX, EndY)) == false) {
continue;
}
WillPush.CurrX = EndX;
WillPush.CurrY = EndY;
Stk.Push(WillPush);
}
}
}
//第3フェーズ 確定探索付の深さ優先探索
static void ExecDFS(char[,] pBanArr)
{
var Stk = new Stack<char[,]>();
char[,] WillPushBanArr = pBanArr;
Stk.Push(WillPushBanArr);
while (Stk.Count > 0) {
char[,] PoppedBanArr = Stk.Pop();
//クリア判定
if (IsClear(PoppedBanArr)) {
Console.WriteLine("解を発見");
PrintAnswer(PoppedBanArr);
return;
}
bool WillBreak = false;
for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
bool WillContinue = true;
if ('1' <= PoppedBanArr[LoopX, LoopY] && PoppedBanArr[LoopX, LoopY] <= '8')
WillContinue = false;
if (WillContinue) continue;
//数値の座標を引数として、設置できるリンクのListを返す
PointDef CurrPoint = new PointDef() { X = LoopX, Y = LoopY };
int StaRestCnt = pBanArr[LoopX, LoopY] - '0';
List<CanSetLinkInfoDef> CanSetLinkList =
DeriveCanSetLinkList(pBanArr, StaRestCnt, CurrPoint);
//閉路ができるリンクをRemove
HeiroRemove(pBanArr, CanSetLinkList, StaRestCnt, CurrPoint);
foreach (CanSetLinkInfoDef EachCanSetLink in CanSetLinkList) {
WillPushBanArr = (char[,])PoppedBanArr.Clone();
SetHashi(WillPushBanArr, EachCanSetLink);
//確定探索を行い、有効な盤面ならPush処理
if (ExecKakuteiTansaku(WillPushBanArr)) {
Stk.Push(WillPushBanArr);
}
}
WillBreak = true;
break;
}
if (WillBreak) break;
}
}
}
//クリア判定
static bool IsClear(char[,] pBanArr)
{
int ZeroX = 0;
int ZeroY = 0;
//数値マスは全て0であること
for (int X = 0; X <= UB_X; X++) {
for (int Y = 0; Y <= UB_Y; Y++) {
if ('1' <= pBanArr[X, Y] && pBanArr[X, Y] <= '8')
return false;
if (pBanArr[X, Y] == '0') {
ZeroX = X; ZeroY = Y;
}
}
}
int ZeroNodeCnt;
bool IsRenketuNonZeroNode;
DeriveZeroNodeShima(pBanArr, new PointDef() { X = ZeroX, Y = ZeroY },
out ZeroNodeCnt, out IsRenketuNonZeroNode);
return ZeroNodeCnt == mNodeCnt && IsRenketuNonZeroNode == false;
}
static string GetHash(int pX, int pY)
{
return string.Format("{0},{1}", pX, pY);
}
static string GetHash(PointDef pPoint)
{
return string.Format("{0},{1}", pPoint.X, pPoint.Y);
}
//解を出力
static void PrintAnswer(char[,] pBanArr)
{
//半角数字を全角数字に変換
Func<int, char> SingleToWideFunc = (pStr) => (char)('０' + pStr - '0');
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 == 'A') sb.Append('ー');
if (CurrChar == 'B') sb.Append('＝');
if (CurrChar == 'C') sb.Append('｜');
if (CurrChar == 'D') sb.Append('‖');
if (CurrChar == ' ') sb.Append(' ');
if ('0' <= CurrChar && CurrChar <= '8')
sb.Append(SingleToWideFunc(mQuestionArr[X, Y]));
}
sb.AppendLine();
}
Console.WriteLine(sb.ToString());
}
}
1 数字と数字の間にタテヨコに橋をかけて(線を引いて)、全体をひとつながりにしましょう。 2 数字は、その数字につながる橋の本数を表します。 3 橋は１カ所に２本までかけられます。 4 橋を交差させたり、ナナメにかけたり、数字を飛び越えてかけたりしてはいけません。