using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
struct PointDef
{
internal int X;
internal int Y;
}
//部屋情報の構造体
struct RoomInfoDef
{
internal char ID; //部屋ID
internal PointDef[] PointArr; //座標の配列
}
static RoomInfoDef[] mRoomInfoArr; //部屋情報の配列
static char[,] mQuestionArr;
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++) {
mQuestionArr[X, Y] = wkArr[Y][X];
}
}
}
static void Main()
{
//問題を定義
QuestionDef();
//第1フェーズ 部屋情報を作成する
CreateRoomInfoArr();
//デバッグ用の部屋情報を出力
//DebugPrintRoomInfo();
//黒マスがB、白マスがW、未確定が半角SPとなる2次元配列
char[,] BlackWhiteArr = new char[UB_X + 1, UB_Y + 1];
for (int X = 0; X <= UB_X; X++) {
for (int Y = 0; Y <= UB_Y; Y++) {
BlackWhiteArr[X, Y] = ' ';
}
}
//第2フェーズ 確定探索
ExecKakuteiTansaku(BlackWhiteArr);
//Console.WriteLine("確定探索後の盤面");
//PrintBan(BlackWhiteArr);
//第3フェーズ 確定探索付の深さ優先探索
ExecDFS(BlackWhiteArr);
}
//第1フェーズ 部屋情報を作成する
static void CreateRoomInfoArr()
{
var RoomInfoDict = new Dictionary<char, List<PointDef>>();
for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
char CurrID = mQuestionArr[LoopX, LoopY];
if (RoomInfoDict.ContainsKey(CurrID) == false) {
RoomInfoDict[CurrID] = new List<PointDef>();
}
PointDef CurrPos = new PointDef() { X = LoopX, Y = LoopY };
RoomInfoDict[CurrID].Add(CurrPos);
}
}
var RoomInfoList = new List<RoomInfoDef>();
foreach (var EachPair in RoomInfoDict) {
RoomInfoDef WillAdd;
WillAdd.ID = EachPair.Key;
WillAdd.PointArr = EachPair.Value.ToArray();
RoomInfoList.Add(WillAdd);
}
mRoomInfoArr = RoomInfoList.ToArray();
}
//デバッグ用の部屋情報を出力
static void DebugPrintRoomInfo()
{
for (int I = 0; I <= mRoomInfoArr.GetUpperBound(0); I++) {
Console.WriteLine("■■■■■■■■■■■■■");
Console.WriteLine("{0}個目の部屋情報", I + 1);
Console.WriteLine("部屋ID={0}", mRoomInfoArr[I].ID);
Console.Write("座標の配列 ");
foreach (var EachPoint in mRoomInfoArr[I].PointArr) {
Console.Write("({0},{1}),", EachPoint.X, EachPoint.Y);
}
Console.WriteLine();
}
}
//第2フェーズ 確定探索を行い有効な盤面かを返す
static bool ExecKakuteiTansaku(char[,] pBlackWhiteArr)
{
while (true) {
char[,] PrevArr = (char[,])pBlackWhiteArr.Clone();
//確定探索1 必要な黒マス数と白マス数が一致する部屋は、黒マスが確定
if (KakuteiTansaku1(pBlackWhiteArr) == false) return false;
//確定探索2 4近傍に空白が1マスしかない黒マスがあったら、その空白は黒マス
KakuteiTansaku2(pBlackWhiteArr);
//確定探索3 4近傍に確定空白しかない白マスは、確定空白
KakuteiTansaku3(pBlackWhiteArr);
//確定探索4 黒マスとすると、3つ以上の黒マスが連結する白マスは、確定空白
KakuteiTansaku4(pBlackWhiteArr);
//確定探索5 黒マスが1つだけある部屋での、確定空白の設定
KakuteiTansaku5(pBlackWhiteArr);
//確定探索6 左と上が黒マスでない、黒マスの右下は、確定空白
KakuteiTansaku6(pBlackWhiteArr);
//確定探索で確定するマスがなくなったらBreak
if (pBlackWhiteArr.Cast<char>().SequenceEqual(PrevArr.Cast<char>())) break;
}
return true;
}
//確定探索1 必要な黒マス数と白マス数が一致する部屋は、黒マスが確定
static bool KakuteiTansaku1(char[,] pBlackWhiteArr)
{
foreach (RoomInfoDef EachRoomInfo in mRoomInfoArr) {
PointDef[] RoomPointArr = EachRoomInfo.PointArr;
int BlackCnt = RoomPointArr.Count(A => pBlackWhiteArr[A.X, A.Y] == 'B');
if (BlackCnt == 2) continue;
int WhiteCnt = RoomPointArr.Count(A => pBlackWhiteArr[A.X, A.Y] == ' ');
int FillCnt = 2 - BlackCnt;
if (FillCnt > WhiteCnt) return false;
if (FillCnt == WhiteCnt) {
foreach (PointDef EachPoint in RoomPointArr) {
if (pBlackWhiteArr[EachPoint.X, EachPoint.Y] == ' ')
SetBlack(EachPoint.X, EachPoint.Y, pBlackWhiteArr);
}
}
}
return true;
}
//確定探索2 4近傍に空白が1マスしかない黒マスがあったら、その空白は黒マス
static void KakuteiTansaku2(char[,] pBlackWhiteArr)
{
for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
if (pBlackWhiteArr[LoopX, LoopY] != 'B') continue;
PointDef[] KinbouPointArr = DeriveKinbouPointArr(LoopX, LoopY);
//黒マスと連結してたら対象外
if (Array.Exists(KinbouPointArr, A => pBlackWhiteArr[A.X, A.Y] == 'B'))
continue;
KinbouPointArr = Array.FindAll(KinbouPointArr, A => pBlackWhiteArr[A.X, A.Y] == ' ');
if (KinbouPointArr.Length == 1) {
SetBlack(KinbouPointArr[0].X, KinbouPointArr[0].Y, pBlackWhiteArr);
}
}
}
}
//確定探索3 4近傍に確定空白しかない白マスは、確定空白
static void KakuteiTansaku3(char[,] pBlackWhiteArr)
{
for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
if (pBlackWhiteArr[LoopX, LoopY] != ' ') continue;
PointDef[] KinbouPointArr = DeriveKinbouPointArr(LoopX, LoopY);
if (Array.TrueForAll(KinbouPointArr, A => pBlackWhiteArr[A.X, A.Y] == 'W')) {
pBlackWhiteArr[LoopX, LoopY] = 'W';
}
}
}
}
//確定探索4 黒マスとすると、3つ以上の黒マスが連結する白マスは、確定空白
static void KakuteiTansaku4(char[,] pBlackWhiteArr)
{
for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
if (pBlackWhiteArr[LoopX, LoopY] != ' ') continue;
char[,] CopiedArr = (char[,])pBlackWhiteArr.Clone();
CopiedArr[LoopX, LoopY] = 'B';
List<PointDef> RenketuBlackPointList =
DeriveRenketuBlackPointList(LoopX, LoopY, CopiedArr);
if (RenketuBlackPointList.Count == 3) {
pBlackWhiteArr[LoopX, LoopY] = 'W';
}
}
}
}
//確定探索5 黒マスが1つだけある部屋での、確定空白の設定
static void KakuteiTansaku5(char[,] pBlackWhiteArr)
{
foreach (RoomInfoDef EachRoomInfo in mRoomInfoArr) {
PointDef[] RoomPointArr = EachRoomInfo.PointArr;
int BlackCnt = RoomPointArr.Count(A => pBlackWhiteArr[A.X, A.Y] == 'B');
if (BlackCnt != 1) continue;
foreach (PointDef EachRoomPoint in RoomPointArr) {
if (pBlackWhiteArr[EachRoomPoint.X, EachRoomPoint.Y] != ' ') continue;
PointDef[] KinbouPointArr =
DeriveKinbouPointArr(EachRoomPoint.X, EachRoomPoint.Y);
//黒マスと連結したマスは対象外
if (Array.Exists(KinbouPointArr, A => pBlackWhiteArr[A.X, A.Y] == 'B'))
continue;
//他の部屋の白マスと隣接したマスは対象外
bool IsRinsetuWhiteMasu = false;
foreach (PointDef EachKinbouPoint in KinbouPointArr) {
//自部屋ならContinue
if (Array.Exists(RoomPointArr,
A => A.X == EachKinbouPoint.X && A.Y == EachKinbouPoint.Y))
continue;
if (pBlackWhiteArr[EachKinbouPoint.X, EachKinbouPoint.Y] == ' ') {
IsRinsetuWhiteMasu = true;
break;
}
}
if (IsRinsetuWhiteMasu) continue;
pBlackWhiteArr[EachRoomPoint.X, EachRoomPoint.Y] = 'W';
}
}
}
//確定探索6 左と上が黒マスでない、黒マスの右下は、確定空白
static void KakuteiTansaku6(char[,] pBlackWhiteArr)
{
for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
if (pBlackWhiteArr[LoopX, LoopY] != 'B') continue;
Action<int, int, int, int> SetAct = (pHeni1_X, pHeni1_Y, pHeni2_X, pHeni2_Y) =>
{
int wk1_X = LoopX + pHeni1_X;
int wk1_Y = LoopY + pHeni1_Y;
int wk2_X = LoopX + pHeni2_X;
int wk2_Y = LoopY + pHeni2_Y;
bool IsKakuteiWhite1 = false;
if (wk1_X < 0 || UB_X < wk1_X
|| wk1_Y < 0 || UB_Y < wk1_Y) IsKakuteiWhite1 = true;
else if (pBlackWhiteArr[wk1_X, wk1_Y] == 'W') IsKakuteiWhite1 = true;
bool IsKakuteiWhite2 = false;
if (wk2_X < 0 || UB_X < wk2_X
|| wk2_Y < 0 || UB_Y < wk2_Y) IsKakuteiWhite2 = true;
else if (pBlackWhiteArr[wk2_X, wk2_Y] == 'W') IsKakuteiWhite2 = true;
if (IsKakuteiWhite1 == false) return;
if (IsKakuteiWhite2 == false) return;
//加算したベクトルの逆ベクトルを使う
int RevX = (pHeni1_X + pHeni2_X) * (-1);
int RevY = (pHeni1_Y + pHeni2_Y) * (-1);
int wk3_X = LoopX + RevX;
int wk3_Y = LoopY + RevY;
if (0 <= wk3_X && wk3_X <= UB_X
&& 0 <= wk3_Y && wk3_Y <= UB_Y) {
pBlackWhiteArr[wk3_X, wk3_Y] = 'W';
}
};
SetAct(0, -1, 1, 0);
SetAct(1, 0, 0, 1);
SetAct(0, 1, -1, 0);
SetAct(-1, 0, 0, -1);
}
}
}
//第3フェーズ 確定探索付の深さ優先探索
static void ExecDFS(char[,] pBlackWhiteArr)
{
var Stk = new Stack<char[,]>();
char[,] WillPushBanArr = pBlackWhiteArr;
Stk.Push(WillPushBanArr);
while (Stk.Count > 0) {
char[,] PoppedBanArr = Stk.Pop();
//クリア判定
bool IsValid;
if (IsClear(PoppedBanArr, out IsValid)) {
Console.WriteLine("解を発見");
PrintBan(PoppedBanArr);
return;
}
if (IsValid == false) continue;
//黒マスの多い部屋を優先して探索する
List<RoomInfoDef> wkRoomInfoList = mRoomInfoArr.ToList();
Func<RoomInfoDef, int> DeriveBlackCnt = (pRoomInfo) =>
pRoomInfo.PointArr.Count(A => pBlackWhiteArr[A.X, A.Y] == 'B');
wkRoomInfoList.RemoveAll(A => DeriveBlackCnt(A) == 2);
wkRoomInfoList.Sort((A, B) => DeriveBlackCnt(B).CompareTo(DeriveBlackCnt(A)));
foreach (RoomInfoDef EachRoomInfo in wkRoomInfoList) {
bool WillBreak = false;
PointDef[] RoomPointArr = EachRoomInfo.PointArr;
foreach (PointDef EachPoint in RoomPointArr) {
if (PoppedBanArr[EachPoint.X, EachPoint.Y] != ' ')
continue;
WillPushBanArr = (char[,])PoppedBanArr.Clone();
SetBlack(EachPoint.X, EachPoint.Y, WillPushBanArr);
//確定探索を行い、有効な盤面ならPush処理
if (ExecKakuteiTansaku(WillPushBanArr)) {
Stk.Push(WillPushBanArr);
}
WillBreak = true;
}
if (WillBreak) break;
}
}
}
//クリア判定
static bool IsClear(char[,] pBlackWhiteArr, out bool pIsValid)
{
pIsValid = true;
//条件1 全ての部屋の黒マスが2マスであること
foreach (RoomInfoDef EachRoomInfo in mRoomInfoArr) {
int BlackCnt = EachRoomInfo.PointArr.Count(A => pBlackWhiteArr[A.X, A.Y] == 'B');
if (BlackCnt < 2) return false;
if (BlackCnt > 2) {
pIsValid = false;
return false;
}
}
//条件2 黒マスが3マス以上連結してないこと
for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
if (pBlackWhiteArr[LoopX, LoopY] != 'B') continue;
List<PointDef> RenketuBlackPointList =
DeriveRenketuBlackPointList(LoopX, LoopY, pBlackWhiteArr);
if (RenketuBlackPointList.Count < 2) return false;
if (RenketuBlackPointList.Count > 2) {
pIsValid = false;
return false;
}
}
}
return true;
}
//座標を引数として、黒マスを設定する
static void SetBlack(int pX, int pY, char[,] pBlackWhiteArr)
{
pBlackWhiteArr[pX, pY] = 'B';
//海苔ができたら、周囲を確定空白にする
List<PointDef> RenketuBlackPointList = DeriveRenketuBlackPointList(pX, pY, pBlackWhiteArr);
if (RenketuBlackPointList.Count == 2) {
foreach (PointDef EachPoint in RenketuBlackPointList) {
PointDef[] KinbouPointArr = DeriveKinbouPointArr(EachPoint.X, EachPoint.Y);
KinbouPointArr = Array.FindAll(KinbouPointArr, A => pBlackWhiteArr[A.X, A.Y] == ' ');
Array.ForEach(KinbouPointArr, A => pBlackWhiteArr[A.X, A.Y] = 'W');
}
}
//部屋の黒マス数が2なら、部屋の白マスを、確定空白にする
char CurrID = mQuestionArr[pX, pY];
int wkInd = Array.FindIndex(mRoomInfoArr, A => A.ID == CurrID);
PointDef[] PointArr = mRoomInfoArr[wkInd].PointArr;
int BlackCnt = PointArr.Count(A => pBlackWhiteArr[A.X, A.Y] == 'B');
if (BlackCnt == 2) {
foreach (PointDef EachPoint in PointArr) {
if (pBlackWhiteArr[EachPoint.X, EachPoint.Y] != ' ') continue;
pBlackWhiteArr[EachPoint.X, EachPoint.Y] = 'W';
}
}
}
struct JyoutaiDefUnionFind
{
internal int CurrX;
internal int CurrY;
}
//座標を引数として、連結した黒マスの座標のListを返す
static List<PointDef> DeriveRenketuBlackPointList(int pStaX, int pStaY, char[,] pBlackWhiteArr)
{
var WillReturn = new List<PointDef>();
WillReturn.Add(new PointDef() { X = pStaX, Y = pStaY });
var Stk = new Stack<JyoutaiDefUnionFind>();
JyoutaiDefUnionFind WillPush;
WillPush.CurrX = pStaX;
WillPush.CurrY = pStaY;
Stk.Push(WillPush);
var VisitedSet = new HashSet<int>();
VisitedSet.Add(pStaX * (UB_Y + 1) + pStaY);
while (Stk.Count > 0) {
JyoutaiDefUnionFind Popped = Stk.Pop();
Action<int, int> PushSyori = (pNewX, pNewY) =>
{
if (pNewX < 0 || UB_X < pNewX) return;
if (pNewY < 0 || UB_Y < pNewY) return;
if (pBlackWhiteArr[pNewX, pNewY] != 'B') return;
//再訪不可
if (VisitedSet.Add(pNewX * (UB_Y + 1) + pNewY) == false)
return;
WillPush.CurrX = pNewX;
WillPush.CurrY = pNewY;
WillReturn.Add(new PointDef() { X = pNewX, Y = 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 WillReturn;
}
//4近傍の座標の配列を返す
static PointDef[] DeriveKinbouPointArr(int pBaseX, int pBaseY)
{
var WillReturnList = new List<PointDef>();
Action<int, int> AddAct = (pX, pY) =>
{
if (pX < 0 || UB_X < pX) return;
if (pY < 0 || UB_Y < pY) return;
WillReturnList.Add(new PointDef() { X = pX, Y = pY });
};
AddAct(pBaseX, pBaseY - 1);
AddAct(pBaseX, pBaseY + 1);
AddAct(pBaseX - 1, pBaseY);
AddAct(pBaseX + 1, pBaseY);
return WillReturnList.ToArray();
}
//盤面を出力
static void PrintBan(char[,] pBlackWhiteArr)
{
var sb = new System.Text.StringBuilder();
for (int Y = 0; Y <= UB_Y; Y++) {
for (int X = 0; X <= UB_X; X++) {
char CurrChar = pBlackWhiteArr[X, Y];
if (CurrChar == 'B') sb.Append('■');
else if (CurrChar == 'W') sb.Append('・');
else sb.Append(mQuestionArr[X, Y]);
}
sb.AppendLine();
}
Console.WriteLine(sb.ToString());
}
}
1 盤面のいくつかのマスを黒くぬりましょう。 2 黒マスは必ずタテかヨコにちょうど２つだけつながったカタマリになります。 3 太線で区切られた各部分には、黒マスが２つずつ入ります。