using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
struct PointDef
{
internal int X;
internal int Y;
}
//部屋情報の構造体
struct RoomInfoDef
{
internal char RoomID; //部屋ID
internal PointDef[] RenketuPointArr; //連結した座標の配列
}
//矢印情報の構造体
struct ArrowInfoDef
{
internal PointDef MaxNumPoint;
internal PointDef[] NonMaxNumPointArr;
}
static char[,] QuestionValArr;
static char[,] QuestionRoomArr;
static int UB_X;
static int UB_Y;
static RoomInfoDef[] RoomInfoArr; //部屋情報の配列
static ArrowInfoDef[] ArrowInfoArr; //矢印情報の配列
static System.Diagnostics.Stopwatch sw = System.Diagnostics.Stopwatch.StartNew();
static void Main()
{
char[,] Q01_ValArr = {{' ' ,' ' ,'←',' ' ,' ' },
{' ' ,' ' ,' ' ,' ' ,'3' },
{' ' ,' ' ,' ' ,' ' ,'←'},
{'→',' ' ,' ' ,' ' ,' ' },
{' ' ,' ' ,'←',' ' ,' ' }};
char[,] Q01_RoomArr = {{'1' ,'1' ,' ' ,'2' ,'2' },
{'3' ,'4' ,'4' ,'2' ,'2' },
{'3' ,'4' ,'5' ,'5' ,' ' },
{' ' ,'6' ,'5' ,'5' ,'7' },
{'6' ,'6' ,' ' ,'7' ,'7' }};
QuestionValArr = XYRev(Q01_ValArr);
QuestionRoomArr = XYRev(Q01_RoomArr);
UB_X = QuestionValArr.GetUpperBound(0);
UB_Y = QuestionValArr.GetUpperBound(1);
//第1フェーズ 部屋情報を作成する
RoomInfoArr = DeriveRoomInfoArr();
//デバッグ用の部屋情報の出力
//DebugPrintRoomInfo();
//第2フェーズ 矢印情報を作成する
ArrowInfoArr = DeriveArrowInfoArr();
//デバッグ用の矢印情報の出力
//DebugPrintArrowInfo();
//第3フェーズ 深さ優先探索
ExecDFS();
}
//第3フェーズの状態Def
struct JyoutaiDef3
{
internal int[,] BanArr; //数値の2次元配列
internal int CurrRoomInfoArrP; //部屋情報の配列の現在の添字
internal int RenketuPointArrP; //連結した座標の配列の現在の添字
}
//X座標とY座標の入れ替え
static char[,] XYRev(char[,] pBaseArr)
{
int RevArrUB_X = pBaseArr.GetUpperBound(1);
int RevArrUB_Y = pBaseArr.GetUpperBound(0);
char[,] WillReturnArr = new char[RevArrUB_X + 1, RevArrUB_Y + 1];
for (int X = 0; X <= RevArrUB_X; X++) {
for (int Y = 0; Y <= RevArrUB_Y; Y++) {
WillReturnArr[X, Y] = pBaseArr[Y, X];
}
}
return WillReturnArr;
}
//第1フェーズ 部屋情報を作成する
static RoomInfoDef[] DeriveRoomInfoArr()
{
var WillReturnList = new List<RoomInfoDef>();
for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
if (QuestionRoomArr[LoopX, LoopY] == ' ')
continue;
//既に部屋情報を作成済かを判定
bool IsCreated = false;
foreach (var EachRoomInfo in WillReturnList) {
if (Array.Exists(EachRoomInfo.RenketuPointArr,
A => A.X == LoopX && A.Y == LoopY))
IsCreated = true;
}
if (IsCreated) continue;
WillReturnList.Add(CreateOneRoomInfo(LoopX, LoopY));
}
}
return WillReturnList.ToArray();
}
//座標を引数として、部屋情報を作成して返す
static RoomInfoDef CreateOneRoomInfo(int pBaseX, int pBaseY)
{
char RoomID = QuestionRoomArr[pBaseX, pBaseY];
//UnionFindで連結した部屋の座標を列挙
var RoomPointList = new List<PointDef>();
var stk = new Stack<PointDef>();
PointDef WillPush;
Action<int, int> PushSyori = (pNewX, pNewY) =>
{
//同じ部屋でない場合
if (QuestionRoomArr[pNewX, pNewY] != RoomID) return;
//訪問済なら再訪できない
if (RoomPointList.Exists(A => A.X == pNewX && A.Y == pNewY))
return;
RoomPointList.Add(new PointDef() { X = pNewX, Y = pNewY });
WillPush.X = pNewX;
WillPush.Y = pNewY;
stk.Push(WillPush);
};
PushSyori(pBaseX, pBaseY);
while (stk.Count > 0) {
PointDef Popped = stk.Pop();
if (Popped.X > 0) PushSyori(Popped.X - 1, Popped.Y); //左に移動
if (Popped.X < UB_X) PushSyori(Popped.X + 1, Popped.Y); //右に移動
if (Popped.Y > 0) PushSyori(Popped.X, Popped.Y - 1); //上に移動
if (Popped.Y < UB_Y) PushSyori(Popped.X, Popped.Y + 1); //下に移動
}
RoomInfoDef WillReturnRoomInfo;
WillReturnRoomInfo.RoomID = RoomID;
//X座標、Y座標の順にソート
WillReturnRoomInfo.RenketuPointArr = RoomPointList.OrderBy(A => A.Y).ThenBy(A => A.X).ToArray();
return WillReturnRoomInfo;
}
//デバッグ用の部屋情報の出力
static void DebugPrintRoomInfo()
{
for (int I = 0; I <= RoomInfoArr.GetUpperBound(0); I++) {
Console.WriteLine("■■■■■■■■■■■■■");
Console.WriteLine("{0}個目の部屋情報", I + 1);
Console.WriteLine("RoomID={0}", RoomInfoArr[I].RoomID);
foreach (var EachNabePoint in RoomInfoArr[I].RenketuPointArr) {
Console.Write("({0},{1}),", EachNabePoint.X, EachNabePoint.Y);
}
Console.WriteLine();
}
}
//第2フェーズ 矢印情報を作成する
static ArrowInfoDef[] DeriveArrowInfoArr()
{
var WillReturnList = new List<ArrowInfoDef>();
for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
bool IsArrowPoint = false;
if (QuestionValArr[LoopX, LoopY] == '↑') IsArrowPoint = true;
if (QuestionValArr[LoopX, LoopY] == '→') IsArrowPoint = true;
if (QuestionValArr[LoopX, LoopY] == '↓') IsArrowPoint = true;
if (QuestionValArr[LoopX, LoopY] == '←') IsArrowPoint = true;
if (IsArrowPoint == false) continue;
WillReturnList.Add(CreateOneArrowInfo(LoopX, LoopY));
}
}
return WillReturnList.ToArray();
}
//座標を引数として、矢印情報を作成して返す
static ArrowInfoDef CreateOneArrowInfo(int pBaseX, int pBaseY)
{
ArrowInfoDef WillReturnArrowInfo;
char CurrArrow = QuestionValArr[pBaseX, pBaseY];
int Heni_X = 0, Heni_Y = 0; //変位ベクトルの値
if (CurrArrow == '↑') Heni_Y = -1;
if (CurrArrow == '→') Heni_X = 1;
if (CurrArrow == '↓') Heni_Y = 1;
if (CurrArrow == '←') Heni_X = -1;
PointDef MaxNumPoint = new PointDef() { X = pBaseX + Heni_X, Y = pBaseY + Heni_Y };
WillReturnArrowInfo.MaxNumPoint = MaxNumPoint;
PointDef[] wkArr = DeriveRinsetuPointArr(pBaseX, pBaseY);
//■の座標と最大値の座標は除外しておく
wkArr = Array.FindAll(wkArr, A => QuestionValArr[A.X, A.Y] != '■');
wkArr = Array.FindAll(wkArr, A => A.X != MaxNumPoint.X || A.Y != MaxNumPoint.Y);
WillReturnArrowInfo.NonMaxNumPointArr = wkArr;
return WillReturnArrowInfo;
}
//指定マスに隣接した座標を配列で返す
static PointDef[] DeriveRinsetuPointArr(int pBaseX, int pBaseY)
{
var WillReturnList = new List<PointDef>();
if (pBaseX > 0)
WillReturnList.Add(new PointDef() { X = pBaseX - 1, Y = pBaseY });
if (pBaseX < UB_X)
WillReturnList.Add(new PointDef() { X = pBaseX + 1, Y = pBaseY });
if (pBaseY > 0)
WillReturnList.Add(new PointDef() { X = pBaseX, Y = pBaseY - 1 });
if (pBaseY < UB_Y)
WillReturnList.Add(new PointDef() { X = pBaseX, Y = pBaseY + 1 });
return WillReturnList.ToArray();
}
//デバッグ用の矢印情報の出力
static void DebugPrintArrowInfo()
{
foreach (var EachArrowInfo in ArrowInfoArr) {
Console.WriteLine("■■■■■■■■■■■■■");
Console.WriteLine("MaxNumPoint=({0},{1})",
EachArrowInfo.MaxNumPoint.X, EachArrowInfo.MaxNumPoint.Y);
for (int I = 0; I <= EachArrowInfo.NonMaxNumPointArr.GetUpperBound(0); I++) {
Console.WriteLine("NonMaxNumPointArr[{0}]=({1},{2})", I,
EachArrowInfo.NonMaxNumPointArr[I].X,
EachArrowInfo.NonMaxNumPointArr[I].Y);
}
}
}
//第3フェーズ 深さ優先探索
static void ExecDFS()
{
var stk = new Stack<JyoutaiDef3>();
JyoutaiDef3 WillPush;
WillPush.BanArr = new int[UB_X + 1, UB_Y + 1];
for (int X = 0; X <= UB_X; X++) {
for (int Y = 0; Y <= UB_Y; Y++) {
char CurrMasu = QuestionValArr[X, Y];
if ('0' <= CurrMasu && CurrMasu <= '9' ||
'A' <= CurrMasu && CurrMasu <= 'Z')
WillPush.BanArr[X, Y] = StrToDec(CurrMasu);
else WillPush.BanArr[X, Y] = 0;
}
}
WillPush.CurrRoomInfoArrP = 0;
WillPush.RenketuPointArrP = 0;
stk.Push(WillPush);
while (stk.Count > 0) {
JyoutaiDef3 Popped = stk.Pop();
//クリア判定
if (Popped.CurrRoomInfoArrP > RoomInfoArr.GetUpperBound(0)) {
Console.WriteLine("解を発見。経過時間={0}", sw.Elapsed);
PrintAnswer(Popped.BanArr);
return;
}
RoomInfoDef CurrRoomInfo = RoomInfoArr[Popped.CurrRoomInfoArrP];
PointDef CurrPoint = CurrRoomInfo.RenketuPointArr[Popped.RenketuPointArrP];
//既に数字が埋まっていた場合
if (Popped.BanArr[CurrPoint.X, CurrPoint.Y] != 0) {
WillPush.BanArr = Popped.BanArr;
WillPush.CurrRoomInfoArrP = Popped.CurrRoomInfoArrP;
WillPush.RenketuPointArrP = Popped.RenketuPointArrP + 1;
int wkUB = RoomInfoArr[WillPush.CurrRoomInfoArrP].RenketuPointArr.GetUpperBound(0);
if (WillPush.RenketuPointArrP > wkUB) {
WillPush.CurrRoomInfoArrP++;
WillPush.RenketuPointArrP = 0;
}
stk.Push(WillPush);
continue;
}
List<int> KouhoNumList = DeriveKouhoNumArr(Popped.BanArr, CurrPoint.X, CurrPoint.Y);
//矢印の4近傍の座標なら候補の数字をRemove
foreach (ArrowInfoDef EachArrowInfo in ArrowInfoArr) {
PointDef MaxNumPoint = EachArrowInfo.MaxNumPoint;
PointDef[] NonMaxNumPointArr = EachArrowInfo.NonMaxNumPointArr;
//矢印の先の座標だった場合
if (MaxNumPoint.X == CurrPoint.X && MaxNumPoint.Y == CurrPoint.Y) {
//NonMaxNumPointArrの最大値より大きいこと
int wkCurrMax = NonMaxNumPointArr.Max(A => Popped.BanArr[A.X, A.Y]);
//NonMaxNumPointArrの要素数が1以上なら、最大値は、最低でも1となる
if (wkCurrMax == 0 && NonMaxNumPointArr.Length > 0) wkCurrMax = 1;
KouhoNumList.RemoveAll(X => X <= wkCurrMax);
}
//矢印の先でないが、矢印の4近傍だった場合
if (Array.Exists(NonMaxNumPointArr, A => A.X == CurrPoint.X && A.Y == CurrPoint.Y)) {
//最大値が0より大きかったら、最大値以上の値は、設定不可
int MaxVal = Popped.BanArr[MaxNumPoint.X, MaxNumPoint.Y];
if (MaxVal > 0) KouhoNumList.RemoveAll(X => MaxVal <= X);
}
}
foreach (int EachKouhoNum in KouhoNumList) {
WillPush.BanArr = (int[,])Popped.BanArr.Clone();
WillPush.BanArr[CurrPoint.X, CurrPoint.Y] = EachKouhoNum;
WillPush.CurrRoomInfoArrP = Popped.CurrRoomInfoArrP;
WillPush.RenketuPointArrP = Popped.RenketuPointArrP + 1;
int wkUB = RoomInfoArr[WillPush.CurrRoomInfoArrP].RenketuPointArr.GetUpperBound(0);
if (WillPush.RenketuPointArrP > wkUB) {
WillPush.CurrRoomInfoArrP++;
WillPush.RenketuPointArrP = 0;
}
stk.Push(WillPush);
}
}
}
//char型を10進数に変換
static int StrToDec(char pStr)
{
if (pStr == ' ') return 0;
if ('A' <= pStr) return 10 + pStr - 'A';
return (int)(pStr - '0');
}
//座標を引数として、矢印情報を加味しないで、配置候補の数値のListを返す
static List<int> DeriveKouhoNumArr(int[,] pBanArr, int pBaseX, int pBaseY)
{
//座標を引数として、部屋で使用可能な数値の配列を返す
List<int> CanUseNumInRoomList = DeriveCanUseNumInRoomList(pBanArr, pBaseX, pBaseY);
//隣接マスで使用済の数値をRemove
PointDef[] RinsetuPointArr = DeriveRinsetuPointArr(pBaseX, pBaseY);
foreach (PointDef EachPoint in RinsetuPointArr) {
CanUseNumInRoomList.Remove(pBanArr[EachPoint.X, EachPoint.Y]);
}
return CanUseNumInRoomList;
}
//座標を引数として、部屋で使用可能な数値のListを返す
static List<int> DeriveCanUseNumInRoomList(int[,] pBanArr, int pBaseX, int pBaseY)
{
var WillReturnList = new List<int>();
foreach (RoomInfoDef EachRoomInfo in RoomInfoArr) {
bool IsHit = false;
foreach (PointDef EachPoint in EachRoomInfo.RenketuPointArr) {
if (EachPoint.X == pBaseX && EachPoint.Y == pBaseY) {
IsHit = true;
break;
}
}
if (IsHit == false) continue;
//1から部屋の座標数が使用可能
for (int I = 1; I <= EachRoomInfo.RenketuPointArr.Length; I++) {
WillReturnList.Add(I);
}
//使用済の数値を除外
foreach (PointDef EachPoint in EachRoomInfo.RenketuPointArr) {
int wkRemoveVal = pBanArr[EachPoint.X, EachPoint.Y];
WillReturnList.Remove(wkRemoveVal);
}
return WillReturnList;
}
return WillReturnList;
}
//解を出力
static void PrintAnswer(int[,] pBanArr)
{
//半角数値を36進数で全角文字に変換
Func<int, char> SingleToWideFunc = (pStr) =>
{
if (pStr <= 9) return (char)('０' + pStr);
return (char)('Ａ' + pStr);
};
var sb = new System.Text.StringBuilder();
for (int Y = 0; Y <= UB_Y; Y++) {
for (int X = 0; X <= UB_X; X++) {
int CurrMasu = pBanArr[X, Y];
if (CurrMasu != 0) sb.Append(SingleToWideFunc(CurrMasu));
else sb.Append(QuestionValArr[X, Y]);
}
sb.AppendLine();
}
Console.WriteLine(sb.ToString());
}
}
char[,] Q02_ValArr = {{'↓',' ' ,' ' ,' ' ,' ' ,' ' ,' ' ,' ' ,' ' ,' ' },
{' ' ,' ' ,'←',' ' ,' ' ,' ' ,'↑',' ' ,' ' ,' ' },
{' ' ,' ' ,' ' ,' ' ,' ' ,' ' ,' ' ,' ' ,' ' ,'↑'},
{' ' ,' ' ,' ' ,' ' ,' ' ,'↓',' ' ,'→',' ' ,' ' },
{' ' ,' ' ,'←',' ' ,' ' ,' ' ,' ' ,' ' ,' ' ,' ' },
{'↑',' ' ,' ' ,' ' ,'↑',' ' ,' ' ,'←',' ' ,' ' },
{' ' ,' ' ,' ' ,' ' ,' ' ,' ' ,' ' ,' ' ,' ' ,' ' },
{' ' ,' ' ,' ' ,'↑',' ' ,' ' ,' ' ,'↓',' ' ,' ' },
{' ' ,' ' ,' ' ,' ' ,' ' ,' ' ,' ' ,' ' ,' ' ,' ' },
{'→',' ' ,' ' ,' ' ,' ' ,' ' ,' ' ,' ' ,' ' ,'↑'}};
char[,] Q02_RoomArr = {{' ' ,'1' ,'2' ,'2' ,'3' ,'4' ,'4' ,'5' ,'5' ,'6' },
{'1' ,'1' ,' ' ,'3' ,'3' ,'4' ,' ' ,'7' ,'7' ,'7' },
{'8' ,'9' ,'9' ,'9' ,'A' ,'B' ,'B' ,'B' ,'C' ,' ' },
{'8' ,'D' ,'D' ,'A' ,'A' ,' ' ,'E' ,' ' ,'C' ,'C' },
{'D' ,'D' ,' ' ,'F' ,'F' ,'F' ,'E' ,'G' ,'G' ,'G' },
{' ' ,'H' ,'H' ,'F' ,' ' ,'I' ,'I' ,' ' ,'G' ,'J' },
{'H' ,'H' ,'K' ,'K' ,'L' ,'L' ,'I' ,'M' ,'M' ,'J' },
{'N' ,'K' ,'K' ,' ' ,'L' ,'O' ,'I' ,' ' ,'M' ,'M' },
{'N' ,'N' ,'P' ,'P' ,'P' ,'O' ,'Q' ,'Q' ,'R' ,'R' },
{' ' ,'S' ,'S' ,'T' ,'T' ,'O' ,'Q' ,'U' ,'R' ,' ' }};
1 盤面のすべての白マスに数字を１つずつ入れましょう。 2 太線で区切られた部分を部屋と呼び、それぞれの部屋には、１からその部屋のマス数までの数を１つずつ入れます。 3 矢印がある黒マスでは、 その黒マスとタテヨコに隣り合う最大４マスのうち、 矢印の前のマスに単独でもっとも大きな数字が入るようにします。 4 同じ数字がタテヨコに隣り合ってはいけません。