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

21-07 JumpIN'

問題

SmartGamesのJumpIN'を解きます。



キノコは、移動できません。
キツネは、前後に移動できます。
ウサギは、前後左右に、キノコかキツネかウサギを1つ以上跳び越す移動ができます。

全てのウサギが●に移動できればクリアです。

Q01
●R□M●
□□M□□
□□●□□
□□M□□
●□R□●

Q02
●□□F●
M□□F□
□M●□R
□□M□□
●□R□●

Q03 (13問目)
●□□M●
□MRFF
□□M□□
□□□□□
●□□□●

Q04 (14問目)
●□□R●
□FF□□
□MM□M
□□□□□
●□□□●

Q05 (15問目)
●□MF●
□□□F□
□□M□□
□□M□R
●□□□●

Q06 (16問目)
●R□□●
M□□□□
M□●□□
□FM□□
●F□□●

Q07 (17問目)
●F□F●
□F□FM
M□●□M
R□□□□
●□□□●

Q08 (18問目)
●□□□●
□□FF□
M□●M□
FF□□□
M□□R●

Q09 (20問目)
●F□R●
□F□M□
□□●□R
□□□FF
●RM□●

Q10
●□□□M
FF□R□
□F●□R
□FM□□
M□□R●


ソース

using System;
using System.Collections.Generic;

class Program
{
    static int mQuestionNo = 2;
    static char[,] mQuestionArr; //問題の初期盤面

    const int UB = 5 - 1;

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

    //問題を定義
    static void QuestionDef()
    {
        string[] wkStrArr = null;
        if (mQuestionNo == 1) {
            wkStrArr = new string[] {"●R□M●",
                                     "□□M□□",
                                     "□□●□□",
                                     "□□M□□",
                                     "●□R□●"};
        }
        if (mQuestionNo == 2) {
            wkStrArr = new string[] {"●□□1●",
                                     "M□□1□",
                                     "□M●□R",
                                     "□□M□□",
                                     "●□R□●"};
        }
        if (mQuestionNo == 3) {
            wkStrArr = new string[] {"●□□M●",
                                     "□MR11",
                                     "□□M□□",
                                     "□□□□□",
                                     "●□□□●"};
        }
        if (mQuestionNo == 4) {
            wkStrArr = new string[] {"●□□R●",
                                     "□11□□",
                                     "□MM□M",
                                     "□□□□□",
                                     "●□□□●"};
        }
        if (mQuestionNo == 5) {
            wkStrArr = new string[] {"●□M1●",
                                     "□□□1□",
                                     "□□M□□",
                                     "□□M□R",
                                     "●□□□●"};
        }
        if (mQuestionNo == 6) {
            wkStrArr = new string[] {"●R□□●",
                                     "M□□□□",
                                     "M□●□□",
                                     "□1M□□",
                                     "●1□□●"};
        }
        if (mQuestionNo == 7) {
            wkStrArr = new string[] {"●1□2●",
                                     "□1□2M",
                                     "M□●□M",
                                     "R□□□□",
                                     "●□□□●"};
        }
        if (mQuestionNo == 8) {
            wkStrArr = new string[] {"●□□□●",
                                     "□□11□",
                                     "M□●M□",
                                     "22□□□",
                                     "M□□R●"};
        }
        if (mQuestionNo == 9) {
            wkStrArr = new string[] {"●1□R●",
                                     "□1□M□",
                                     "□□●□R",
                                     "□□□22",
                                     "●RM□●"};
        }
        if (mQuestionNo == 10) {
            wkStrArr = new string[] {"●□□□M",
                                     "11□R□",
                                     "□2●□R",
                                     "□2M□□",
                                     "M□□R●"};
        }

        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];
    }

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

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

        //幅優先探索で解く
        var Que = new Queue<JyoutaiDef>();
        JyoutaiDef WillEnqueue;
        WillEnqueue.Level = 0;
        WillEnqueue.BanArr = mQuestionArr;
        WillEnqueue.Log = new List<char[,]>() { WillEnqueue.BanArr };
        Que.Enqueue(WillEnqueue);

        //訪問済の盤面
        var VisitedSet = new HashSet<string>();
        VisitedSet.Add(GetHash(WillEnqueue.BanArr));

        while (Que.Count > 0) {
            JyoutaiDef Dequeued = Que.Dequeue();

            //クリア判定
            if (IsClear(Dequeued.BanArr)) {
                Console.WriteLine("解を発見");

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

            for (int LoopX = 0; LoopX <= UB; LoopX++) {
                for (int LoopY = 0; LoopY <= UB; LoopY++) {
                    // 移動後の盤面のList
                    var MoveList = new List<char[,]>();

                    //ウサギの座標の場合
                    if (Dequeued.BanArr[LoopX, LoopY] == 'R') {
                        MoveList = DeriveUsagiMoveList(Dequeued.BanArr, LoopX, LoopY);
                    }

                    //キツネの左上座標の場合
                    int FoxHeniX, FoxHeniY;
                    if (GetFoxInfo(Dequeued.BanArr, LoopX, LoopY, out FoxHeniX, out FoxHeniY)) {
                        MoveList = DeriveFoxMoveList(Dequeued.BanArr, LoopX, LoopY, FoxHeniX, FoxHeniY);
                    }

                    foreach (char[,] EachMove in MoveList) {
                        WillEnqueue.Level = Dequeued.Level + 1;
                        WillEnqueue.BanArr = EachMove;
                        WillEnqueue.Log = new List<char[,]>(Dequeued.Log) { WillEnqueue.BanArr };

                        string CurrHash = GetHash(WillEnqueue.BanArr);

                        if (VisitedSet.Add(CurrHash)) {
                            Que.Enqueue(WillEnqueue);
                        }
                    }
                }
            }
        }
    }

    //クリア判定
    static bool IsClear(char[,] pBanArr)
    {
        for (int Y = 0; Y <= UB; Y++) {
            for (int X = 0; X <= UB; X++) {
                if (pBanArr[X, Y] != 'R') continue;
                if (IsHole(X, Y) == false) return false;
            }
        }
        return true;
    }

    //穴が存在する座標かを返す
    static bool IsHole(int pX, int pY)
    {
        if (pX == 0 && pY == 0) return true;
        if (pX == 0 && pY == UB) return true;
        if (pX == UB && pY == 0) return true;
        if (pX == UB && pY == UB) return true;
        if (pX == UB / 2 && pY == UB / 2) return true;
        return false;
    }

    //座標を引数として、移動後のマスを返す
    static char DeriveMovedMasu(int pX, int pY)
    {
        if (IsHole(pX, pY)) return '●';
        return '□';
    }

    //盤面の内部かを返す
    static bool IsInside(int pX, int pY)
    {
        if (pX < 0 || UB < pX) return false;
        if (pY < 0 || UB < pY) return false;
        return true;
    }

    //ウサギがジャンプ後の盤情報の配列を返す
    static List<char[,]> DeriveUsagiMoveList(char[,] pBanArr, int pFromX, int pFromY)
    {
        var WillReturn = new List<char[,]>();

        Action<int, int, int> MoveAct = (pHeniX, pHeniY, pAbs) =>
        {
            int GoalX = pFromX + pHeniX * pAbs;
            int GoalY = pFromY + pHeniY * pAbs;

            if (IsInside(GoalX, GoalY) == false) return;
            if (pBanArr[GoalX, GoalY] != '●' &&
                pBanArr[GoalX, GoalY] != '□') return;

            //移動先までの間に、ウサギ、キノコ、キツネのいずれかがあること
            for (int LoopAbs = 1; LoopAbs <= pAbs - 1; LoopAbs++) {
                int CheckX = pFromX + pHeniX * LoopAbs;
                int CheckY = pFromY + pHeniY * LoopAbs;

                bool IsOK = false;
                if (pBanArr[CheckX, CheckY] == 'R') IsOK = true;
                if (pBanArr[CheckX, CheckY] == 'M') IsOK = true;
                if (pBanArr[CheckX, CheckY] == '1') IsOK = true;
                if (pBanArr[CheckX, CheckY] == '2') IsOK = true;
                if (IsOK == false) return;
            }

            //移動元を変更
            char[,] WillAdd = (char[,])pBanArr.Clone();
            WillAdd[pFromX, pFromY] = DeriveMovedMasu(pFromX, pFromY);

            //移動先を変更
            WillAdd[GoalX, GoalY] = 'R';

            WillReturn.Add(WillAdd);
        };

        //移動先のループ
        for (int I = 2; I <= UB; I++) {
            MoveAct(0, -1, I);
            MoveAct(0, +1, I);
            MoveAct(+1, 0, I);
            MoveAct(-1, 0, I);
        }

        return WillReturn;
    }

    //キツネの左上座標かを返す
    static bool GetFoxInfo(char[,] pBanArr, int pCurrX, int pCurrY, out int pFoxHeniX, out int pFoxHeniY)
    {
        pFoxHeniX = pFoxHeniY = 0;

        char CurrMasu = pBanArr[pCurrX, pCurrY];
        if (CurrMasu != '1' && CurrMasu != '2') return false;

        //下に連結している場合
        if (IsInside(pCurrX, pCurrY + 1)) {
            if (pBanArr[pCurrX, pCurrY + 1] == CurrMasu) {
                pFoxHeniX = 0; pFoxHeniY = 1;
                return true;
            }
        }

        //右に連結している場合
        if (IsInside(pCurrX + 1, pCurrY)) {
            if (pBanArr[pCurrX + 1, pCurrY] == CurrMasu) {
                pFoxHeniX = 1; pFoxHeniY = 0;
                return true;
            }
        }

        //キツネの座標だが、左上の座標でない場合
        return false;
    }

    //キツネが移動後の盤情報の配列を返す
    static List<char[,]> DeriveFoxMoveList(char[,] pBanArr, int pFromX, int pFromY,
                                                            int pFoxHeniX, int pFoxHeniY)
    {
        var WillReturn = new List<char[,]>();

        char CurrMasu = pBanArr[pFromX, pFromY];

        //移動前のキツネの座標のList
        var BeforeFoxPosList = new List<PointDef>();
        BeforeFoxPosList.Add(new PointDef() { X = pFromX, Y = pFromY });
        BeforeFoxPosList.Add(new PointDef() { X = pFromX + pFoxHeniX, Y = pFromY + pFoxHeniY });

        foreach (int EachAbs in (new int[] { -1, 1 })) {
            bool CanMove = true;

            //移動後のキツネの座標のList
            var AfterFoxPosList = new List<PointDef>();
            foreach (PointDef EachFoxPos in BeforeFoxPosList) {
                int TargetX = EachFoxPos.X + pFoxHeniX * EachAbs;
                int TargetY = EachFoxPos.Y + pFoxHeniY * EachAbs;

                if (IsInside(TargetX, TargetY) == false) {
                    CanMove = false;
                    break;
                }

                if (pBanArr[TargetX, TargetY] == '□'
                 || pBanArr[TargetX, TargetY] == CurrMasu) {

                    AfterFoxPosList.Add(new PointDef() { X = TargetX, Y = TargetY });
                }
                else CanMove = false;
            }

            if (CanMove) {
                char[,] WillAdd = (char[,])pBanArr.Clone();
                BeforeFoxPosList.ForEach(pEach => WillAdd[pEach.X, pEach.Y] = '□');
                AfterFoxPosList.ForEach(pEach => WillAdd[pEach.X, pEach.Y] = CurrMasu);

                WillReturn.Add(WillAdd);
            }
        }
        return WillReturn;
    }

    //盤面をハッシュ値に変換
    static string GetHash(char[,] pBanArr)
    {
        var sb = new System.Text.StringBuilder();

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

    //盤面を出力
    static void PrintBan(char[,] pBanArr)
    {
        var sb = new System.Text.StringBuilder();
        for (int Y = 0; Y <= UB; Y++) {
            for (int X = 0; X <= UB; X++) {
                sb.Append(pBanArr[X, Y]);
            }
            sb.AppendLine();
        }
        Console.WriteLine(sb.ToString());
    }
}


実行結果

解を発見
レベル0
●□□1●
M□□1□
□M●□R
□□M□□
●□R□●

レベル1
●□□1●
M□□1□
□MR□R
□□M□□
●□□□●

レベル2
●□□□●
M□□1□
□MR1R
□□M□□
●□□□●

レベル3
●□□□●
M□□1□
RMR1□
□□M□□
●□□□●

レベル4
R□□□●
M□□1□
□MR1□
□□M□□
●□□□●


解説

幅優先探索で解いてます。