using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
//ラインごとの候補の構造体
struct KouhoInfoDef
{
internal bool IsXZahyou;
internal int Zahyou;
internal List<char[]> KouhoArrList;
}
static List<int[]> QuestionXNumArrList;
static List<int[]> QuestionYNumArrList;
static int UB_X;
static int UB_Y;
static KouhoInfoDef[] KouhoInfoArr; //ラインごとの候補の配列
static System.Diagnostics.Stopwatch sw = System.Diagnostics.Stopwatch.StartNew();
static void Main()
{
List<int[]> Q01_XNumArrList = new List<int[]>();
Q01_XNumArrList.Add(new int[] { 3 });
Q01_XNumArrList.Add(new int[] { 4 });
Q01_XNumArrList.Add(new int[] { 4 });
Q01_XNumArrList.Add(new int[] { 11 });
Q01_XNumArrList.Add(new int[] { 2, 1 });
Q01_XNumArrList.Add(new int[] { 1, 2, 2 });
Q01_XNumArrList.Add(new int[] { 2, 1, 3 });
Q01_XNumArrList.Add(new int[] { 1, 2, 4 });
Q01_XNumArrList.Add(new int[] { 1, 1, 3 });
Q01_XNumArrList.Add(new int[] { 11 });
List<int[]> Q01_YNumArrList = new List<int[]>();
Q01_YNumArrList.Add(new int[] { 4 });
Q01_YNumArrList.Add(new int[] { 3, 1 });
Q01_YNumArrList.Add(new int[] { 2, 1 });
Q01_YNumArrList.Add(new int[] { 1, 3 });
Q01_YNumArrList.Add(new int[] { 1, 3, 1 });
Q01_YNumArrList.Add(new int[] { 3, 1 });
Q01_YNumArrList.Add(new int[] { 1, 1 });
Q01_YNumArrList.Add(new int[] { 1, 1 });
Q01_YNumArrList.Add(new int[] { 1, 1 });
Q01_YNumArrList.Add(new int[] { 1, 3 });
Q01_YNumArrList.Add(new int[] { 2, 4 });
Q01_YNumArrList.Add(new int[] { 3, 4 });
Q01_YNumArrList.Add(new int[] { 4, 3 });
Q01_YNumArrList.Add(new int[] { 3 });
Q01_YNumArrList.Add(new int[] { 2 });
List<int[]> Q02_XNumArrList = new List<int[]>();
Q02_XNumArrList.Add(new int[] { 4 });
Q02_XNumArrList.Add(new int[] { 2, 8 });
Q02_XNumArrList.Add(new int[] { 2, 2, 3 });
Q02_XNumArrList.Add(new int[] { 3, 1, 1, 2 });
Q02_XNumArrList.Add(new int[] { 1, 2, 2, 1, 2 });
Q02_XNumArrList.Add(new int[] { 1, 3, 1, 1 });
Q02_XNumArrList.Add(new int[] { 1, 3, 4, 1 });
Q02_XNumArrList.Add(new int[] { 1, 1, 1, 1 });
Q02_XNumArrList.Add(new int[] { 1, 4, 2 });
Q02_XNumArrList.Add(new int[] { 1, 4, 2 });
Q02_XNumArrList.Add(new int[] { 1, 2, 2, 3 });
Q02_XNumArrList.Add(new int[] { 3, 8 });
Q02_XNumArrList.Add(new int[] { 2, 7 });
Q02_XNumArrList.Add(new int[] { 2, 7 });
Q02_XNumArrList.Add(new int[] { 4 });
List<int[]> Q02_YNumArrList = new List<int[]>();
Q02_YNumArrList.Add(new int[] { 9 });
Q02_YNumArrList.Add(new int[] { 2, 2 });
Q02_YNumArrList.Add(new int[] { 4, 4 });
Q02_YNumArrList.Add(new int[] { 2, 7, 2 });
Q02_YNumArrList.Add(new int[] { 1, 2, 2, 1 });
Q02_YNumArrList.Add(new int[] { 1, 6, 1 });
Q02_YNumArrList.Add(new int[] { 5, 3, 2 });
Q02_YNumArrList.Add(new int[] { 2, 1, 4 });
Q02_YNumArrList.Add(new int[] { 1, 1, 3 });
Q02_YNumArrList.Add(new int[] { 1, 1, 3 });
Q02_YNumArrList.Add(new int[] { 1, 4, 3 });
Q02_YNumArrList.Add(new int[] { 1, 3 });
Q02_YNumArrList.Add(new int[] { 2, 4 });
Q02_YNumArrList.Add(new int[] { 4, 5 });
Q02_YNumArrList.Add(new int[] { 10 });
List<int[]> Q03_XNumArrList = new List<int[]>();
Q03_XNumArrList.Add(new int[] { 1 });
Q03_XNumArrList.Add(new int[] { 1 });
Q03_XNumArrList.Add(new int[] { 0 });
List<int[]> Q03_YNumArrList = new List<int[]>();
Q03_YNumArrList.Add(new int[] { 1 });
Q03_YNumArrList.Add(new int[] { 1 });
Q03_YNumArrList.Add(new int[] { 0 });
QuestionXNumArrList = Q01_XNumArrList;
QuestionYNumArrList = Q01_YNumArrList;
UB_X = QuestionXNumArrList.Count - 1;
UB_Y = QuestionYNumArrList.Count - 1;
//第1フェーズ ラインごとの候補を列挙
KouhoInfoArr = DeriveKouhoInfoArr();
//デバッグ用 ラインごとの候補の出力
//DebugPrintKouhoInfo();
char[,] 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++) {
BanArr[X, Y] = ' ';
}
}
//第2フェーズ ラインごとの全候補との共通部分を設定
KakuteiTansaku(BanArr);
//第3フェーズ 確定探索付の深さ優先探索
ExecDFS(BanArr);
}
//第1フェーズ ラインごとの候補を列挙
static KouhoInfoDef[] DeriveKouhoInfoArr()
{
var WillReturnList = new List<KouhoInfoDef>();
for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
KouhoInfoDef WillAdd;
WillAdd.IsXZahyou = true;
WillAdd.Zahyou = LoopX;
WillAdd.KouhoArrList = DeriveKouhoInfoArrHelper(WillAdd.IsXZahyou, WillAdd.Zahyou);
WillReturnList.Add(WillAdd);
}
for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
KouhoInfoDef WillAdd;
WillAdd.IsXZahyou = false;
WillAdd.Zahyou = LoopY;
WillAdd.KouhoArrList = DeriveKouhoInfoArrHelper(WillAdd.IsXZahyou, WillAdd.Zahyou);
WillReturnList.Add(WillAdd);
}
return WillReturnList.ToArray();
}
//ラインごとの候補を列挙する探索の状態Def
struct JyotaiDef1
{
internal int LineNumArrP;
internal char[] LineKouhoArr;
}
//第1フェーズ ラインごとの候補を列挙
static List<char[]> DeriveKouhoInfoArrHelper(bool pIsXZahyou, int pZahyou)
{
var WillReturnList = new List<char[]>();
int[] LineNumArr = (pIsXZahyou ? QuestionXNumArrList[pZahyou] :
QuestionYNumArrList[pZahyou]);
int UB = (pIsXZahyou ? UB_Y : UB_X); //固定する軸がX軸なら、Y座標のUBとなる
//0だけの特殊ケース
if (LineNumArr[0] == 0) {
char[] wkArr = new char[UB + 1];
for (int I = 0; I <= UB; I++) wkArr[I] = '/';
WillReturnList.Add(wkArr);
return WillReturnList;
}
var stk = new Stack<JyotaiDef1>();
JyotaiDef1 WillPush;
WillPush.LineNumArrP = 0;
WillPush.LineKouhoArr = new char[UB + 1];
for (int I = 0; I <= UB; I++) WillPush.LineKouhoArr[I] = ' ';
stk.Push(WillPush);
while (stk.Count > 0) {
JyotaiDef1 Popped = stk.Pop();
//終了判定
int wkLineKouhoArrP = Array.FindIndex(Popped.LineKouhoArr, A => A == ' ');
if (wkLineKouhoArrP < 0) {
if (Popped.LineNumArrP > LineNumArr.GetUpperBound(0))
WillReturnList.Add(Popped.LineKouhoArr);
continue;
}
//黒マスを埋めるケース
if (Popped.LineNumArrP <= LineNumArr.GetUpperBound(0)) {
int wkNum = LineNumArr[Popped.LineNumArrP];
int RestMasuCnt = UB - wkLineKouhoArrP + 1;
//黒マスを埋められなければ無効な状態
if (RestMasuCnt < wkNum) continue;
//黒マスで埋める
WillPush.LineKouhoArr = (char[])Popped.LineKouhoArr.Clone();
for (int I = wkLineKouhoArrP; I <= wkLineKouhoArrP + wkNum - 1; I++) {
WillPush.LineKouhoArr[I] = '*';
}
//残りマスがあったら確定空白となる
int NewLineInd = wkLineKouhoArrP + wkNum;
if (NewLineInd <= UB)
WillPush.LineKouhoArr[NewLineInd] = '/';
//Push処理
WillPush.LineNumArrP = Popped.LineNumArrP + 1;
stk.Push(WillPush);
}
//確定空白とするケース
WillPush.LineKouhoArr = (char[])Popped.LineKouhoArr.Clone();
WillPush.LineKouhoArr[wkLineKouhoArrP] = '/';
WillPush.LineNumArrP = Popped.LineNumArrP;
stk.Push(WillPush);
}
return WillReturnList;
}
//デバッグ用 ラインごとの候補の出力
static void DebugPrintKouhoInfo()
{
foreach (KouhoInfoDef EachKouhoInfo in KouhoInfoArr) {
Console.WriteLine("■■■■■■■■■■■■■");
Console.WriteLine("{0}{1}",
EachKouhoInfo.IsXZahyou ? "X座標" : "Y座標", EachKouhoInfo.Zahyou);
for (int I = 0; I <= EachKouhoInfo.KouhoArrList.Count - 1; I++) {
Console.WriteLine("候補{0}", I + 1);
Array.ForEach<char>(EachKouhoInfo.KouhoArrList[I], A => Console.Write(A));
Console.WriteLine();
}
}
}
//第2フェーズ ラインごとの全候補との共通部分を設定し
//有効な盤面かを返す
static bool KakuteiTansaku(char[,] pBanArr)
{
while (true) {
char[,] PrevBanArr = (char[,])pBanArr.Clone();
for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
char[] wkLineArr = new char[UB_Y + 1];
for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
wkLineArr[LoopY] = pBanArr[LoopX, LoopY];
}
//ラインごとの全候補での共通部分を設定
bool IsSet;
if (KakuteiTansakuHelper(wkLineArr, true, LoopX, out IsSet) == false)
return false;
if (IsSet == false) continue;
for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
pBanArr[LoopX, LoopY] = wkLineArr[LoopY];
}
}
for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
char[] wkLineArr = new char[UB_X + 1];
for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
wkLineArr[LoopX] = pBanArr[LoopX, LoopY];
}
//ラインごとの全候補での共通部分を設定
bool IsSet;
if (KakuteiTansakuHelper(wkLineArr, false, LoopY, out IsSet) == false)
return false;
if (IsSet == false) continue;
for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
pBanArr[LoopX, LoopY] = wkLineArr[LoopX];
}
}
//確定探索で確定するマスがなくなったらBreak
if (pBanArr.Cast<char>().SequenceEqual(PrevBanArr.Cast<char>())) break;
}
return true;
}
//確定探索2 ラインごとの全候補での共通部分を設定し
//有効な盤面かを返す
static bool KakuteiTansakuHelper(char[] pLineArr, bool pIsXZahyou, int pZahyou, out bool pIsSet)
{
pIsSet = false;
//ラインの現在の状態を引数として候補の配列のListを返す
List<char[]> wkKouhoArrList = DeriveKouhoArrList(pLineArr, pIsXZahyou, pZahyou);
if (wkKouhoArrList.Count == 0) return false;
//全候補での共通部分を設定
for (int I = 0; I <= pLineArr.GetUpperBound(0); I++) {
if (pLineArr[I] != ' ') continue;
IEnumerable<char> wkEnum = wkKouhoArrList.Select(A => A[I]).Distinct();
if (wkEnum.Count() == 1) {
pLineArr[I] = wkEnum.First();
pIsSet = true;
}
}
return true;
}
//ラインの現在の状態を引数として候補の配列のListを返す
static List<char[]> DeriveKouhoArrList(char[] pLineArr, bool pIsXZahyou, int pZahyou)
{
KouhoInfoDef KouhoInfo = Array.Find(KouhoInfoArr, A => A.IsXZahyou == pIsXZahyou
&& A.Zahyou == pZahyou);
List<char[]> wkKouhoArrList = new List<char[]>();
KouhoInfo.KouhoArrList.ForEach(A => wkKouhoArrList.Add((char[])A.Clone()));
//空白以外で差異がある候補をRemove
for (int I = wkKouhoArrList.Count - 1; 0 <= I; I--) {
bool WillRemove = false;
for (int J = 0; J <= pLineArr.GetUpperBound(0); J++) {
if (pLineArr[J] == ' ') continue;
if (pLineArr[J] != wkKouhoArrList[I][J]) {
WillRemove = true;
break;
}
}
if (WillRemove) wkKouhoArrList.RemoveAt(I);
}
return wkKouhoArrList;
}
//仮置きする深さ優先探索の状態Def
struct JyotaiDef3
{
internal char[,] BanArr;
}
//第3フェーズ 確定探索付の深さ優先探索
static void ExecDFS(char[,] pBanArr)
{
var stk = new Stack<JyotaiDef3>();
JyotaiDef3 WillPush;
WillPush.BanArr = pBanArr;
stk.Push(WillPush);
while (stk.Count > 0) {
JyotaiDef3 Popped = stk.Pop();
//空白マスのあるX座標を求める
int SpaceXZahyou = DeriveSpaceXZahyou(Popped.BanArr);
//クリア判定
if (SpaceXZahyou == -1) {
Console.WriteLine("解を発見。経過時間={0}", sw.Elapsed);
PrintAnswer(Popped.BanArr);
continue;
}
char[] wkLineArr = new char[UB_Y + 1];
for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
wkLineArr[LoopY] = pBanArr[SpaceXZahyou, LoopY];
}
//ラインの現在の状態を引数として候補の配列のListを返す
List<char[]> wkKouhoArrList = DeriveKouhoArrList(wkLineArr, true, SpaceXZahyou);
foreach (char[] EachKouhoArr in wkKouhoArrList) {
WillPush.BanArr = (char[,])Popped.BanArr.Clone();
for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
WillPush.BanArr[SpaceXZahyou, LoopY] = EachKouhoArr[LoopY];
}
if (KakuteiTansaku(WillPush.BanArr))
stk.Push(WillPush);
}
}
}
//空白マスのあるX座標を求める
static int DeriveSpaceXZahyou(char[,] pBanArr)
{
for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
if (pBanArr[LoopX, LoopY] == ' ') return LoopX;
}
}
return -1;
}
//解を出力
static void PrintAnswer(char[,] pBanArr)
{
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('×');
if (CurrMasu == '*') sb.Append('■');
if (CurrMasu == ' ') sb.Append('□');
}
sb.AppendLine();
}
Console.WriteLine(sb.ToString());
}
}
問2
