using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
struct PointDef
{
internal int X;
internal int Y;
}
//鍋情報の構造体
struct NabeInfoDef
{
internal int NeedGuzai; //必要な具材の数、未指定なら0
internal PointDef[] RenketuPointArr; //連結した鍋の座標の配列
}
//具材情報の構造体
struct GuzaiInfoDef
{
internal int CntGuzai; //具材の数
internal PointDef Point; //具材の座標
internal PointDef[] CanMoveNabePointArr; //移動可能な鍋の座標の配列
}
static char[,] QuestionGuzaiArr;
static int[,] QuestionBanNumArr;
static int UB_X;
static int UB_Y;
static NabeInfoDef[] NabeInfoArr; //鍋情報の配列
static GuzaiInfoDef[] GuzaiInfoArr; //具材情報の配列
static System.Diagnostics.Stopwatch sw = System.Diagnostics.Stopwatch.StartNew();
static void Main()
{
char[,] Q01_GuzaiArr = {{'○',' ' ,'■','■','■'},
{' ' ,' ' ,'○',' ' ,' ' },
{' ' ,'■','■','■','○'},
{' ' ,' ' ,' ' ,'○',' ' },
{'■','■','○',' ' ,'■'}};
int[,] Q01_BanNumArr = {{ 5, 0, 4, 0, 0},
{ 0, 0, 2, 0, 0},
{ 0, 0, 0, 0, 2},
{ 0, 0, 0, 4, 0},
{ 6, 0, 1, 0, 0}};
QuestionGuzaiArr = XYRev<char>(Q01_GuzaiArr);
QuestionBanNumArr = XYRev<int>(Q01_BanNumArr);
UB_X = QuestionGuzaiArr.GetUpperBound(0);
UB_Y = QuestionGuzaiArr.GetUpperBound(1);
//第1フェーズ 鍋情報を作成する
NabeInfoArr = DeriveNabeInfoArr();
//デバッグ用の鍋情報の出力
//DebugPrintNabeInfo();
//第2フェーズ 具材情報を作成する
GuzaiInfoArr = DeriveGuzaiInfoArr();
//具材情報の配列から、具材の値のほうが大きい鍋を、移動可能鍋からRemove
RemoveInValidCanMoveNabe();
//デバッグ用の具材情報の出力
//DebugPrintGuzaiInfo();
//第3フェーズ 鍋に具材を入れる
ExecGuzaiIntoNabe();
}
//X座標とY座標の入れ替え
static AnyType[,] XYRev<AnyType>(AnyType[,] pBaseArr)
{
int RevArrUB_X = pBaseArr.GetUpperBound(1);
int RevArrUB_Y = pBaseArr.GetUpperBound(0);
AnyType[,] WillReturnArr = new AnyType[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 NabeInfoDef[] DeriveNabeInfoArr()
{
var WillReturnList = new List<NabeInfoDef>();
for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
if (QuestionGuzaiArr[LoopX, LoopY] != '■')
continue;
//既に鍋情報を作成済かを判定
bool IsCreated = false;
foreach (var EachNabeInfo in WillReturnList) {
if (Array.Exists(EachNabeInfo.RenketuPointArr,
A => A.X == LoopX && A.Y == LoopY))
IsCreated = true;
}
if (IsCreated) continue;
WillReturnList.Add(CreateOneNabeInfo(LoopX, LoopY));
}
}
//必要な具材の数の昇順(ただし、0は最後とする)
return WillReturnList.OrderBy(A => A.NeedGuzai == 0).ThenBy(A => A.NeedGuzai).ToArray();
}
//座標を引数として、鍋情報を作成して返す
static NabeInfoDef CreateOneNabeInfo(int pBaseX, int pBaseY)
{
//UnionFindで連結した鍋の座標を列挙
var NumPointList = new List<PointDef>();
var stk = new Stack<PointDef>();
PointDef WillPush;
Action<int, int> PushSyori = (pNewX, pNewY) =>
{
//鍋でない場合
if (QuestionGuzaiArr[pNewX, pNewY] != '■') return;
//訪問済なら再訪できない
if (NumPointList.Exists(A => A.X == pNewX && A.Y == pNewY))
return;
NumPointList.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); //下に移動
}
NabeInfoDef WillReturnNabeInfo;
//X座標、Y座標の順にソート
WillReturnNabeInfo.RenketuPointArr = NumPointList.OrderBy(A => A.Y).ThenBy(A => A.X).ToArray();
WillReturnNabeInfo.NeedGuzai = 0;
//連結した鍋の中に数字マスを含むかを判定
foreach (var EachPoint in NumPointList) {
int wkNum = QuestionBanNumArr[EachPoint.X, EachPoint.Y];
if (wkNum != 0) {
WillReturnNabeInfo.NeedGuzai = wkNum;
break;
}
}
return WillReturnNabeInfo;
}
//デバッグ用の鍋情報の出力
static void DebugPrintNabeInfo()
{
for (int I = 0; I <= NabeInfoArr.GetUpperBound(0); I++) {
Console.WriteLine("■■■■■■■■■■■■■");
Console.WriteLine("{0}個目の鍋情報", I + 1);
Console.WriteLine("具材数={0}", NabeInfoArr[I].NeedGuzai);
foreach (var EachNabePoint in NabeInfoArr[I].RenketuPointArr) {
Console.Write("({0},{1}),", EachNabePoint.X, EachNabePoint.Y);
}
Console.WriteLine();
}
}
//第2フェーズ 具材情報を作成する
static GuzaiInfoDef[] DeriveGuzaiInfoArr()
{
var WillReturnList = new List<GuzaiInfoDef>();
for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
if (QuestionGuzaiArr[LoopX, LoopY] != '○')
continue;
GuzaiInfoDef WillAdd;
WillAdd.CntGuzai = QuestionBanNumArr[LoopX, LoopY];
WillAdd.Point = new PointDef() { X = LoopX, Y = LoopY };
WillAdd.CanMoveNabePointArr = CreateCanMoveNabePointArr(LoopX, LoopY);
WillReturnList.Add(WillAdd);
}
}
return WillReturnList.ToArray();
}
//具材の座標を引数として、移動可能な鍋の座標の配列を返す
static PointDef[] CreateCanMoveNabePointArr(int pBaseX, int pBaseY)
{
var WillReturnList = new List<PointDef>();
Action<int, int> CheckAct = (pHeni_X, pHeni_Y) =>
{
//追加済の移動可能な鍋のID
var AddedNabeIDSet = new HashSet<int>();
int LoopX = pBaseX;
int LoopY = pBaseY;
while (true) {
//次のマスからがチェック対象となる
LoopX += pHeni_X; LoopY += pHeni_Y;
//範囲外の場合
if (LoopX < 0 || UB_X < LoopX) return;
if (LoopY < 0 || UB_Y < LoopY) return;
//鍋の場合
if (QuestionGuzaiArr[LoopX, LoopY] == '■') {
//既に追加済の鍋IDかを判定
int wkInd = -1;
for (int I = 0; I <= NabeInfoArr.GetUpperBound(0); I++) {
if (Array.Exists(NabeInfoArr[I].RenketuPointArr,
A => A.X == LoopX && A.Y == LoopY)) {
wkInd = I; break;
}
}
if (AddedNabeIDSet.Add(wkInd) == false) continue;
WillReturnList.Add(new PointDef() { X = LoopX, Y = LoopY });
}
//別の具材があった場合
if (QuestionGuzaiArr[LoopX, LoopY] == '○') return;
}
};
CheckAct(0, -1); CheckAct(0, +1);
CheckAct(+1, 0); CheckAct(-1, 0);
return WillReturnList.ToArray();
}
//デバッグ用の具材情報の出力
static void DebugPrintGuzaiInfo()
{
foreach (var EachGuzaiInfo in GuzaiInfoArr) {
Console.WriteLine("■■■■■■■■■■■■■");
Console.WriteLine("具材の座標=({0},{1}),具材の数={2}",
EachGuzaiInfo.Point.X, EachGuzaiInfo.Point.Y, EachGuzaiInfo.CntGuzai);
foreach (var EachPoint in EachGuzaiInfo.CanMoveNabePointArr) {
Console.WriteLine("移動可能な座標({0},{1})", EachPoint.X, EachPoint.Y);
}
}
}
//具材情報の配列から、具材の値のほうが大きい鍋を、移動可能鍋からRemove
static void RemoveInValidCanMoveNabe()
{
for (int I = 0; I <= GuzaiInfoArr.GetUpperBound(0); I++) {
List<PointDef> wkList = GuzaiInfoArr[I].CanMoveNabePointArr.ToList();
for (int J = wkList.Count - 1; 0 <= J; J--) {
PointDef wkPoint = new PointDef() { X = wkList[J].X, Y = wkList[J].Y };
var tmp1 = NabeInfoArr.Where(A => A.NeedGuzai > 0);
var tmp2 = tmp1.Where(A => A.NeedGuzai < GuzaiInfoArr[I].CntGuzai);
foreach (var EachNabeInfo in tmp2) {
if (Array.Exists(EachNabeInfo.RenketuPointArr,
A => A.X == wkPoint.X && A.Y == wkPoint.Y)) {
wkList.RemoveAt(J);
break;
}
}
}
GuzaiInfoArr[I].CanMoveNabePointArr = wkList.ToArray();
}
}
//第3フェーズの状態Def
struct JyoutaiDef3
{
internal char[,] BanArr; //具材の移動した矢印の2次元配列
internal int CurrNabeInfoArrP; //鍋情報の配列の現在の添字
internal int CurrGuzaiInfoArrP; //具材情報の配列の現在の添字
internal List<int> UsedGuzaiList; //使用済の具材の添字のList
internal int CurrGuzaiSum; //現在の鍋の具材の合計
}
//第3フェーズ 鍋に具材を入れる
static void ExecGuzaiIntoNabe()
{
var stk = new Stack<JyoutaiDef3>();
JyoutaiDef3 WillPush;
WillPush.BanArr = 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 CurrMasu = QuestionGuzaiArr[X, Y];
WillPush.BanArr[X, Y] = (CurrMasu == '○' ? '○' : ' ');
}
}
WillPush.CurrNabeInfoArrP = WillPush.CurrGuzaiInfoArrP = 0;
WillPush.UsedGuzaiList = new List<int>();
WillPush.CurrGuzaiSum = 0;
stk.Push(WillPush);
while (stk.Count > 0) {
JyoutaiDef3 Popped = stk.Pop();
//クリア判定
if (Popped.CurrNabeInfoArrP > NabeInfoArr.GetUpperBound(0)) {
//余った具材の有無をチェック
if (Popped.UsedGuzaiList.Count == GuzaiInfoArr.Length) {
Console.WriteLine("解を発見。経過時間={0}", sw.Elapsed);
PrintAnswer(Popped.BanArr);
}
continue;
}
//カレントの鍋情報
NabeInfoDef CurrNabeInfo = NabeInfoArr[Popped.CurrNabeInfoArrP];
//具材情報の配列でループ
for (int I = 0; I <= GuzaiInfoArr.GetUpperBound(0); I++) {
//具材情報の配列の現在の添字未満の場合
if (I < Popped.CurrGuzaiInfoArrP) continue;
//使用済の具材の場合
if (Popped.UsedGuzaiList.Contains(I)) continue;
//具材の数がオーバーする場合
if (CurrNabeInfo.NeedGuzai > 0
&& CurrNabeInfo.NeedGuzai < Popped.CurrGuzaiSum + GuzaiInfoArr[I].CntGuzai)
continue;
//具材が移動可能な鍋の座標でループ
foreach (var EachCanMoveNabePoint in GuzaiInfoArr[I].CanMoveNabePointArr) {
//当該の鍋に移動不可な具材を除外
if (Array.Exists(CurrNabeInfo.RenketuPointArr,
A => A.X == EachCanMoveNabePoint.X
&& A.Y == EachCanMoveNabePoint.Y) == false) {
continue;
}
//他の具材の移動によって移動不可になってないかを判定
WillPush.BanArr = (char[,])Popped.BanArr.Clone();
PointDef GuzaiPoint;
GuzaiPoint.X = GuzaiInfoArr[I].Point.X;
GuzaiPoint.Y = GuzaiInfoArr[I].Point.Y;
PointDef NabePoint;
NabePoint.X = EachCanMoveNabePoint.X;
NabePoint.Y = EachCanMoveNabePoint.Y;
if (MoveGuzai(WillPush.BanArr, GuzaiPoint, NabePoint) == false)
continue;
WillPush.CurrNabeInfoArrP = Popped.CurrNabeInfoArrP;
WillPush.CurrGuzaiInfoArrP = I + 1;
WillPush.UsedGuzaiList = new List<int>(Popped.UsedGuzaiList) { I };
WillPush.CurrGuzaiSum = Popped.CurrGuzaiSum + GuzaiInfoArr[I].CntGuzai;
//具材数が指定されてる鍋の場合 (鍋変更は、指定数に到達した場合のみ)
if (CurrNabeInfo.NeedGuzai > 0) {
if (CurrNabeInfo.NeedGuzai == WillPush.CurrGuzaiSum) {
//次の鍋がカレントになる
WillPush.CurrNabeInfoArrP++;
WillPush.CurrGuzaiInfoArrP = 0;
WillPush.CurrGuzaiSum = 0;
}
stk.Push(WillPush);
}
else { //具材数が未指定の鍋の場合
//現在の鍋がそのままカレント
stk.Push(WillPush);
//少なくとも1つの具材が設定されていれば、次の鍋をカレントに設定
if (WillPush.CurrGuzaiSum > 0) {
WillPush.CurrNabeInfoArrP++;
WillPush.CurrGuzaiInfoArrP = 0;
WillPush.CurrGuzaiSum = 0;
stk.Push(WillPush);
}
}
}
}
}
}
//具材を鍋に移動させる。移動不可だったらFalseを返す
static bool MoveGuzai(char[,] pBanArr, PointDef pGuzaiPoint, PointDef pNabePoint)
{
int GuzaiX = pGuzaiPoint.X, GuzaiY = pGuzaiPoint.Y;
int NabeX = pNabePoint.X, NabeY = pNabePoint.Y;
//変位ベクトルの値
int Heni_X = Math.Sign(NabeX - GuzaiX);
int Heni_Y = Math.Sign(NabeY - GuzaiY);
int LoopX = GuzaiX, LoopY = GuzaiY;
do {
//次のマスからが埋める候補となる
LoopX += Heni_X; LoopY += Heni_Y;
//移動可能でない場合
if (pBanArr[LoopX, LoopY] != ' ') return false;
if (Heni_X == 0 && Heni_Y == -1) pBanArr[LoopX, LoopY] = '↑';
if (Heni_X == 0 && Heni_Y == 1) pBanArr[LoopX, LoopY] = '↓';
if (Heni_X == -1 && Heni_Y == 0) pBanArr[LoopX, LoopY] = '←';
if (Heni_X == 1 && Heni_Y == 0) pBanArr[LoopX, LoopY] = '→';
} while ((LoopX == NabeX && LoopY == NabeY) == false);
return true;
}
//解を出力
static void PrintAnswer(char[,] pBanArr)
{
//半角数字を全角数字に変換
Func<int, char> SingleToWideFunc = (pStr) => (char)('０' + pStr);
var sb = new System.Text.StringBuilder();
for (int Y = 0; Y <= UB_Y; Y++) {
for (int X = 0; X <= UB_X; X++) {
char CurrMasu = pBanArr[X, Y];
if (CurrMasu == '↑') sb.Append(CurrMasu);
else if (CurrMasu == '→') sb.Append(CurrMasu);
else if (CurrMasu == '↓') sb.Append(CurrMasu);
else if (CurrMasu == '←') sb.Append(CurrMasu);
else {
CurrMasu = QuestionGuzaiArr[X, Y];
if (CurrMasu == ' ') sb.Append(" ");
else if (CurrMasu == '○') {
int wkInt = QuestionBanNumArr[X, Y];
if (wkInt <= 9) sb.Append(SingleToWideFunc(wkInt));
else sb.Append(wkInt.ToString());
}
else sb.Append(CurrMasu);
}
}
sb.AppendLine();
}
Console.WriteLine(sb.ToString());
}
}
1 すべての白丸（具材）をタテかヨコにまっすぐ移動させて、灰色のエリア(鍋)に入れましょう。 2 白丸の移動は矢印で表します。矢印の先端はマスの中央になります。 矢印は途中で折れ曲がらず、他の白丸や矢印の線とぶつかることもありません。 3 灰色のエリアにある数字は、そこに入る白丸の数字の合計と等しくなります。 数字のないエリアでは合計数はわかりませんが、少なくとも１つは白丸が入ります。