トップページに戻る    次のC#のサンプルへ    前のC#のサンプルへ

22-09 Tip Over

問題

ThinkfunのTip Overを解きます。




Tipperは、クレートを上下左右のいずれかの方向に倒すことができます。
青クレートは倒すと4マス。
緑クレートは倒すと3マス。
黄クレートは倒すと2マス。
になります。

Tipperは、クレート(倒したクレートを含む)の上を移動することができます。
Tipperが、赤クレートに到達すればクリアです。

Q01
初期位置は、[5,1]の青マス
□□□□□□
緑□□□□青
□□□□□黄
□□□□□□
□□□□□□
黄□□赤□□

Q02 (Beginnerの1)
初期位置は、[1,3]の黄マス
□□□□□□
□黄□□□□
赤□□□□□
□黄緑□□□
□緑□□□□
□□□□□□

Q03 (Intermediateの1)
初期位置は、[1,4]の青マス
□□□□□□
□□□□□□
□□□□□□
□□黄緑□赤
□青黄□□□
□□□□青□

Q04 (Advancedの1)
初期位置は、[2,3]の黄マス
□□□□□□
□青□黄□□
赤□黄青黄□
□黄黄□□□
□□□□□□
□□□黄黄□

Q05 (Expertの1)
初期位置は、[0,2]の黄マス
青□□□□□
緑緑□□□□
黄黄□□緑□
□黄□□□□
□□□□□青
□赤□□□□

Q06 (Expertの2)
初期位置は、[3,3]の黄マス
□□□□□□
□緑□□□□
黄緑□□□□
黄緑黄黄□□
□□□黄黄青
赤□□□□□

Q07 (Expertの3)
初期位置は、[2,0]の黄マス
□□黄□□□
□黄□黄□□
□□□黄黄黄
□黄黄□□黄
赤□緑□□□
□黄□□□□

Q08 (Expertの4)
初期位置は、[1,4]の黄マス
□黄□黄□□
□□□□黄□
□□黄□□□
□黄黄黄黄□
青黄□□□赤
□□□□黄□


ソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static int mQuestionNo = 1;
    static char[,] mQuestionArr; //問題の初期盤面
    static PointDef mStaPos;
    static List<PointDef> mCratePosList = new List<PointDef>();

    const int UB = 5;

    struct PointDef
    {
        internal int X;
        internal int Y;
    }

    //問題を定義
    static void QuestionDef()
    {
        string[] wkStrArr = null;
        if (mQuestionNo == 1) {
            wkStrArr = new string[] {"□□□□□□",
                                     "緑□□□□青",
                                     "□□□□□黄",
                                     "□□□□□□",
                                     "□□□□□□",
                                     "黄□□赤□□"};
            mStaPos.X = 5; mStaPos.Y = 1;
        }
        if (mQuestionNo == 2) {
            wkStrArr = new string[] {"□□□□□□",
                                     "□黄□□□□",
                                     "赤□□□□□",
                                     "□黄緑□□□",
                                     "□緑□□□□",
                                     "□□□□□□"};
            mStaPos.X = 1; mStaPos.Y = 3;
        }
        if (mQuestionNo == 3) {
            wkStrArr = new string[] {"□□□□□□",
                                     "□□□□□□",
                                     "□□□□□□",
                                     "□□黄緑□赤",
                                     "□青黄□□□",
                                     "□□□□青□"};
            mStaPos.X = 1; mStaPos.Y = 4;
        }
        if (mQuestionNo == 4) {
            wkStrArr = new string[] {"□□□□□□",
                                     "□青□黄□□",
                                     "赤□黄青黄□",
                                     "□黄黄□□□",
                                     "□□□□□□",
                                     "□□□黄黄□"};
            mStaPos.X = 2; mStaPos.Y = 3;
        }
        if (mQuestionNo == 5) {
            wkStrArr = new string[] {"青□□□□□",
                                     "緑緑□□□□",
                                     "黄黄□□緑□",
                                     "□黄□□□□",
                                     "□□□□□青",
                                     "□赤□□□□"};
            mStaPos.X = 0; mStaPos.Y = 2;
        }
        if (mQuestionNo == 6) {
            wkStrArr = new string[] {"□□□□□□",
                                     "□緑□□□□",
                                     "黄緑□□□□",
                                     "黄緑黄黄□□",
                                     "□□□黄黄青",
                                     "赤□□□□□"};
            mStaPos.X = 3; mStaPos.Y = 3;
        }
        if (mQuestionNo == 7) {
            wkStrArr = new string[] {"□□黄□□□",
                                     "□黄□黄□□",
                                     "□□□黄黄黄",
                                     "□黄黄□□黄",
                                     "赤□緑□□□",
                                     "□黄□□□□"};
            mStaPos.X = 2; mStaPos.Y = 0;
        }
        if (mQuestionNo == 8) {
            wkStrArr = new string[] {"□黄□黄□□",
                                     "□□□□黄□",
                                     "□□黄□□□",
                                     "□黄黄黄黄□",
                                     "青黄□□□赤",
                                     "□□□□黄□"};
            mStaPos.X = 1; mStaPos.Y = 4;
        }

        mQuestionArr = new char[UB + 1, UB + 1];
        for (int Y = 0; Y <= UB; Y++)
            for (int X = 0; X <= UB; X++)
                mQuestionArr[Y, X] = wkStrArr[X][Y];

        for (int X = 0; X <= UB; X++) {
            for (int Y = 0; Y <= UB; Y++) {
                if (mQuestionArr[X, Y] == '□') continue;

                PointDef WillAdd;
                WillAdd.X = X;
                WillAdd.Y = Y;
                mCratePosList.Add(WillAdd);
            }
        }
    }

    struct JyoutaiDef
    {
        internal int Level;
        internal char[,] BanArr;
        internal PointDef CurrPos;
        internal List<string> Log;
    }

    static void Main()
    {
        //問題を定義
        QuestionDef();

        var Stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.Level = 0;
        WillPush.BanArr = mQuestionArr;
        WillPush.CurrPos = mStaPos;
        WillPush.Log = new List<string>() { BanToStr(WillPush.BanArr, WillPush.CurrPos) };
        Stk.Push(WillPush);

        int AnswerLevel = int.MaxValue;
        List<string> AnswerLog = null;

        while (Stk.Count > 0) {
            JyoutaiDef Popped = Stk.Pop();

            //移動可能な座標のListを返す
            List<PointDef> CanMovePosList = DeriveCanMovePosList(Popped.BanArr, Popped.CurrPos);

            if (IsClear(Popped.BanArr, CanMovePosList)) {
                if (Popped.Level < AnswerLevel) {
                    AnswerLevel = Popped.Level;
                    AnswerLog = Popped.Log;
                }
                continue;
            }

            //下限値枝切り
            if (AnswerLevel <= Popped.Level) continue;

            foreach (PointDef EachCanMovePos in CanMovePosList) {
                int MovedX = EachCanMovePos.X;
                int MovedY = EachCanMovePos.Y;

                //移動先が倒せるクレートでない場合
                int CrateInd = mCratePosList.FindIndex(A => A.X == MovedX && A.Y == MovedY);
                if (CrateInd == -1) continue;

                if (Popped.BanArr[MovedX, MovedY] == '■') continue;

                int CrateLength = 0;
                char CrateColor = Popped.BanArr[MovedX, MovedY];
                if (CrateColor == '青') CrateLength = 4;
                if (CrateColor == '緑') CrateLength = 3;
                if (CrateColor == '黄') CrateLength = 2;

                Action<int, int> TaosuAct = (pHeniX, pHeniY) =>
                {
                    char[,] wkArr = (char[,])Popped.BanArr.Clone();

                    for (int I = 1; I <= CrateLength; I++) {
                        int CurrX = MovedX + pHeniX * I;
                        int CurrY = MovedY + pHeniY * I;

                        if (CurrX < 0 || UB < CurrX) return;
                        if (CurrY < 0 || UB < CurrY) return;

                        //空欄でない場合
                        if (Popped.BanArr[CurrX, CurrY] != '□') return;

                        wkArr[CurrX, CurrY] = '■';
                    }
                    wkArr[MovedX, MovedY] = '□';

                    WillPush.Level = Popped.Level + 1;
                    WillPush.BanArr = wkArr;

                    PointDef wkPos;
                    wkPos.X = MovedX + pHeniX * CrateLength;
                    wkPos.Y = MovedY + pHeniY * CrateLength;
                    WillPush.CurrPos = wkPos;

                    WillPush.Log = new List<string>(Popped.Log);
                    WillPush.Log.Add(BanToStr(WillPush.BanArr, WillPush.CurrPos));
                    Stk.Push(WillPush);
                };

                TaosuAct(0, -1);
                TaosuAct(0, +1);
                TaosuAct(-1, 0);
                TaosuAct(+1, 0);
            }
        }
        for (int I = 0; I <= AnswerLog.Count - 1; I++) {
            Console.WriteLine("レベル{0}", I);
            Console.WriteLine(AnswerLog[I]);
        }
    }

    //移動可能な座標のListを返す
    static List<PointDef> DeriveCanMovePosList(char[,] pBanArr, PointDef pCurrPos)
    {
        var WillReturn = new List<PointDef>() { pCurrPos };

        var Stk = new Stack<PointDef>();
        Stk.Push(pCurrPos);

        var VisitedSet = new HashSet<string>();
        VisitedSet.Add(string.Format("({0},{1})", pCurrPos.X, pCurrPos.Y));

        while (Stk.Count > 0) {
            PointDef Popped = Stk.Pop();

            Action<int, int> PushSyori = (pNewX, pNewY) =>
            {
                if (pNewX < 0 || UB < pNewX) return;
                if (pNewY < 0 || UB < pNewY) return;

                //空欄は訪問不可
                if (pBanArr[pNewX, pNewY] == '□') return;

                //再訪防止
                string wkStr = string.Format("({0},{1})", pNewX, pNewY);
                if (VisitedSet.Add(wkStr) == false) return;

                PointDef wkPos = new PointDef() { X = pNewX, Y = pNewY };
                WillReturn.Add(wkPos);
                Stk.Push(wkPos);
            };

            PushSyori(Popped.X, Popped.Y - 1);
            PushSyori(Popped.X, Popped.Y + 1);
            PushSyori(Popped.X - 1, Popped.Y);
            PushSyori(Popped.X + 1, Popped.Y);
        }
        return WillReturn;
    }

    //クリア判定
    static bool IsClear(char[,] pBanArr, List<PointDef> pCanMovePosList)
    {
        for (int X = 0; X <= UB; X++) {
            for (int Y = 0; Y <= UB; Y++) {
                if (mQuestionArr[X, Y] != '赤') continue;

                return pCanMovePosList.Exists(A => A.X == X && A.Y == Y);
            }
        }
        return false;
    }

    //盤面をString型に変換
    static string BanToStr(char[,] pBanArr, PointDef pCurrPos)
    {
        var sb = new System.Text.StringBuilder();

        int CurrX = pCurrPos.X;
        int CurrY = pCurrPos.Y;

        sb.AppendFormat("Tipperは、[{0},{1}]に存在", CurrX, CurrY);
        sb.AppendLine();

        for (int Y = 0; Y <= UB; Y++) {
            for (int X = 0; X <= UB; X++) {
                sb.Append(pBanArr[X, Y]);
            }
            sb.AppendLine();
        }
        return sb.ToString();
    }
}


実行結果

レベル0
Tipperは、[5,1]に存在
□□□□□□
緑□□□□青
□□□□□黄
□□□□□□
□□□□□□
黄□□赤□□

レベル1
Tipperは、[1,1]に存在
□□□□□□
緑■■■■□
□□□□□黄
□□□□□□
□□□□□□
黄□□赤□□

レベル2
Tipperは、[0,4]に存在
□□□□□□
□■■■■□
■□□□□黄
■□□□□□
■□□□□□
黄□□赤□□

レベル3
Tipperは、[2,5]に存在
□□□□□□
□■■■■□
■□□□□黄
■□□□□□
■□□□□□
□■■赤□□


解説

深さ優先探索で解いてます。