using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static int UB_X;
static int UB_Y;
struct JyoutaiDef
{
internal int Level;
internal char[,] BanArr;
}
struct PointDef
{
internal int X;
internal int Y;
}
static void Main()
{
var stk = new Stack<JyoutaiDef>();
JyoutaiDef WillPush;
bool IsSentaisyou=false; //問題が線対称か？
IsSentaisyou = true;
char[,] Q1Arr = new char[,] {{' ','*','*',' '},
{'*','*','*','*'}};
IsSentaisyou = false;
char[,] Q2Arr = new char[,] {{' ','*','*'},
{'*',' ',' '},
{' ',' ','*'},
{'*','*',' '}};
IsSentaisyou = false;
char[,] Q9Arr = new char[,] {{'*','*','*','*'},
{'*',' ',' ',' '},
{'*','*','*',' '},
{'*',' ',' ',' '},
{'*',' ',' ',' '},
{'*',' ',' ',' '}};
IsSentaisyou = false;
char[,] Q10Arr = new char[,] {{' ',' ',' ','*'},
{' ',' ','*','*'},
{' ','*',' ','*'},
{'*','*','*','*'}};
char[,] RevArr = Q9Arr;
//縦横変換してセット
UB_X = RevArr.GetUpperBound(1);
UB_Y = RevArr.GetUpperBound(0);
char[,] wkArr = new char[UB_X + 1, UB_Y + 1];
for (int X = 0; X <= UB_X; X++) {
for (int Y = 0; Y <= UB_Y; Y++) {
wkArr[X, Y] = RevArr[Y, X];
}
}
//開始位置の数だけStackにPush
for (int Y = 0; Y <= UB_Y; Y++) {
for (int X = 0; X <= UB_X; X++) {
//線対称な解を除外
if (IsSentaisyou && UB_X / 2 < X) break;
if (wkArr[X, Y] != '*') continue;
WillPush.Level = 1;
WillPush.BanArr = (char[,])wkArr.Clone();
WillPush.BanArr[X, Y] = '1';
stk.Push(WillPush);
}
}
int AnwserCnt = 0;
while (stk.Count > 0) {
JyoutaiDef Popped = stk.Pop();
//クリア判定
if (Popped.BanArr.Cast<char>().All(X => X != '*')) {
Console.WriteLine("解{0}を発見", ++AnwserCnt);
PrintAnswer(Popped.BanArr);
continue;
}
//移動可能な座標の配列
PointDef[] CanMovePointArr =
DeriveCanMovePointArr(Popped.Level, Popped.BanArr);
foreach (PointDef EachPoint in CanMovePointArr) {
WillPush.Level = Popped.Level + 1;
WillPush.BanArr = (char[,])Popped.BanArr.Clone();
WillPush.BanArr[EachPoint.X, EachPoint.Y] = DecToStr(WillPush.Level);
stk.Push(WillPush);
}
}
}
//10進数をchar型に変換
static char DecToStr(int pInt)
{
if (pInt < 10) return (char)((int)'1' + pInt - 1);
return (char)((int)'A' + pInt - 10);
}
//移動可能な座標の配列を返す
static PointDef[] DeriveCanMovePointArr(int pCurrLevel, char[,] pBanArr)
{
var CanMovePointList = new List<PointDef>();
//Levelを元に、現在地を求める
PointDef CurrPoint = DeriveLevelPoint(pCurrLevel, pBanArr);
var HeniList = new List<PointDef>();
HeniList.Add(new PointDef() { X = 0, Y = -1 });
HeniList.Add(new PointDef() { X = 0, Y = 1 });
HeniList.Add(new PointDef() { X = -1, Y = 0 });
HeniList.Add(new PointDef() { X = 1, Y = 0 });
if (pCurrLevel >= 2) {
//Levelを元に、ひとつ前の位置を求める
PointDef PrevPoint = DeriveLevelPoint(pCurrLevel - 1, pBanArr);
//直近の移動の変位ベクトルを求める
PointDef PrevHeni;
PrevHeni.X = CurrPoint.X - PrevPoint.X;
PrevHeni.Y = CurrPoint.Y - PrevPoint.Y;
if (PrevHeni.X > 1) PrevHeni.X = 1;
if (PrevHeni.X < -1) PrevHeni.X = -1;
if (PrevHeni.Y > 1) PrevHeni.Y = 1;
if (PrevHeni.Y < -1) PrevHeni.Y = -1;
//逆ベクトルを変位ベクトルのListからRemove(バックできないから)
HeniList.RemoveAll(A => A.X == -PrevHeni.X && A.Y == -PrevHeni.Y);
}
//変位ごとに、拾う石があったら、移動可能な座標となる
foreach (PointDef EachHeni in HeniList) {
for (PointDef wkPoint = CurrPoint;
0 <= wkPoint.X && wkPoint.X <= UB_X &&
0 <= wkPoint.Y && wkPoint.Y <= UB_Y;
wkPoint.X += EachHeni.X, wkPoint.Y += EachHeni.Y) {
if (pBanArr[wkPoint.X, wkPoint.Y] == '*') {
CanMovePointList.Add(wkPoint);
break;
}
}
}
return CanMovePointList.ToArray();
}
//引数のレベルの座標を返す
static PointDef DeriveLevelPoint(int pTargetLevel, char[,] pBanArr)
{
PointDef WillReturn = new PointDef() { X = -1, Y = -1 };
for (int X = 0; X <= UB_X; X++) {
for (int Y = 0; Y <= UB_Y; Y++) {
if (pBanArr[X, Y] != DecToStr(pTargetLevel)) continue;
WillReturn.X = X;
WillReturn.Y = Y;
return WillReturn;
}
}
return WillReturn;
}
//解を出力
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++) {
sb.Append(pBanArr[X, Y]);
}
sb.AppendLine();
}
Console.WriteLine(sb.ToString());
}
}
Cマガ電脳クラブ(第043回) ひろいものと同じルールです。 Q1 □●●□ ●●●● Q2 □●● ●□□ □□● ●●□ Q9 ●●●● ●□□□ ●●●□ ●□□□ ●□□□ Q10 □□□● □□●● □●□● ●●●●