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

22-02 Hoppers

問題

ThinkfunのHoppersを解きます。

     

カエルは、縦か横か斜め45度に、1匹のカエルを跳び越して移動します。
跳び越されたカエルは、盤上から取り去ります。

赤カエルだけが残ればクリアです。
(赤カエルがいない問題では、いずれかの緑カエルが残ればクリアです)

同じカエルが動き続ける限り1手として、最少手数で解きます。

Q1
緑 ○ ○
 緑 ○
○ 緑 ○
 赤 ○
○ ○ ○

Q2
緑 緑 ○
 緑 緑
緑 ○ ○
 赤 緑
○ ○ ○

Q3
緑 緑 ○
 緑 ○
○ 緑 緑
 ○ 緑
○ ○ 緑

Q4 (追加問題の1)
○ ○ 緑
 緑 緑
緑 ○ 緑
 緑 緑
緑 緑 ○

Q5 (追加問題の2)
○ ○ ○
 緑 緑
緑 ○ 緑
 緑 緑
緑 緑 緑

Q6 (追加問題の3)
○ 緑 ○
 緑 緑
緑 緑 緑
 緑 緑
緑 ○ 緑

Q7 (追加問題の4)
○ 緑 緑
 緑 緑
緑 ○ ○
 緑 緑
緑 緑 緑


ソース

using System;
using System.Collections.Generic;

class Program
{
    static int mQuestionNo = 1;
    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[] {"緑 ○ ○",
                                     " 緑 ○ ",
                                     "○ 緑 ○",
                                     " 赤 ○ ",
                                     "○ ○ ○"};
        }
        if (mQuestionNo == 2) {
            wkStrArr = new string[] {"緑 緑 ○",
                                     " 緑 緑 ",
                                     "緑 ○ ○",
                                     " 赤 緑 ",
                                     "○ ○ ○"};
        }
        if (mQuestionNo == 3) {
            wkStrArr = new string[] {"緑 緑 ○",
                                     " 緑 ○ ",
                                     "○ 緑 緑",
                                     " ○ 緑 ",
                                     "○ ○ 緑"};
        }
        if (mQuestionNo == 4) {
            wkStrArr = new string[] {"○ ○ 緑",
                                     " 緑 緑 ",
                                     "緑 ○ 緑",
                                     " 緑 緑 ",
                                     "緑 緑 ○"};
        }
        if (mQuestionNo == 5) {
            wkStrArr = new string[] {"○ ○ ○",
                                     " 緑 緑 ",
                                     "緑 ○ 緑",
                                     " 緑 緑 ",
                                     "緑 緑 緑"};
        }
        if (mQuestionNo == 6) {
            wkStrArr = new string[] {"○ 緑 ○",
                                     " 緑 緑 ",
                                     "緑 緑 緑",
                                     " 緑 緑 ",
                                     "緑 ○ 緑"};
        }
        if (mQuestionNo == 7) {
            wkStrArr = new string[] {"○ 緑 緑",
                                     " 緑 緑 ",
                                     "緑 ○ ○",
                                     " 緑 緑 ",
                                     "緑 緑 緑"};
        }

        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 PointDef CurrPos;
        internal List<char[,]> Log;
    }

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

        var Stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.Level = 0;
        WillPush.BanArr = mQuestionArr;
        WillPush.CurrPos = new PointDef() { X = -1, Y = -1 };
        WillPush.Log = new List<char[,]>() { WillPush.BanArr };
        Stk.Push(WillPush);

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

            //クリア判定
            if (IsClear(Popped.BanArr)) {
                if (Popped.Level < AnswerLevel) {
                    AnswerLevel = Popped.Level;
                    Console.WriteLine("{0}手の解候補を発見", Popped.Level);
                    for (int I = 0; I <= Popped.Log.Count - 1; I++) {
                        Console.WriteLine("レベル{0}", I);
                        PrintBan(Popped.Log[I]);
                    }
                }
                continue;
            }
            //下限値枝切り
            if (AnswerLevel <= Popped.Level) continue;

            for (int LoopX = 0; LoopX <= UB; LoopX++) {
                for (int LoopY = 0; LoopY <= UB; LoopY++) {
                    if (Popped.BanArr[LoopX, LoopY] != '緑'
                     && Popped.BanArr[LoopX, LoopY] != '赤') continue;
                    JumpedInfoDef[] JumpedInfoArr =
                        DeriveJumpedInfoArr(Popped.BanArr, LoopX, LoopY);

                    foreach (JumpedInfoDef EachJumoedInfo in JumpedInfoArr) {
                        if (Popped.CurrPos.X != LoopX || Popped.CurrPos.Y != LoopY)
                            WillPush.Level = Popped.Level + 1;
                        else WillPush.Level = Popped.Level;

                        WillPush.BanArr = EachJumoedInfo.BanArr;
                        WillPush.CurrPos = EachJumoedInfo.NewCurrPos;
                        WillPush.Log = new List<char[,]>(Popped.Log) { WillPush.BanArr };
                        Stk.Push(WillPush);
                    }
                }
            }
        }
    }

    //クリア判定
    static bool IsClear(char[,] pBanArr)
    {
        int KaeruCnt = 0;
        for (int LoopX = 0; LoopX <= UB; LoopX++) {
            for (int LoopY = 0; LoopY <= UB; LoopY++) {
                if (pBanArr[LoopX, LoopY] == '緑') KaeruCnt++;
                if (pBanArr[LoopX, LoopY] == '赤') KaeruCnt++;
            }
        }
        return KaeruCnt == 1;
    }

    //ジャンプ後の盤情報
    struct JumpedInfoDef
    {
        internal char[,] BanArr;
        internal PointDef NewCurrPos;
    }

    //カエルのジャンプ後の盤情報の配列を返す
    static JumpedInfoDef[] DeriveJumpedInfoArr(char[,] pBanArr, int pFromX, int pFromY)
    {
        var WillReturn = new List<JumpedInfoDef>();

        Action<int, int> JumpAct = (pHeniX, pHeniY) =>
        {
            if (CanJump(pBanArr, pFromX, pFromY, pHeniX, pHeniY) == false)
                return;

            char[,] wkArr = (char[,])pBanArr.Clone();
            wkArr[pFromX, pFromY] = '○';
            wkArr[pFromX + pHeniX, pFromY + pHeniY] = '○';
            wkArr[pFromX + pHeniX * 2, pFromY + pHeniY * 2] = pBanArr[pFromX, pFromY];

            JumpedInfoDef WillAdd;
            WillAdd.BanArr = wkArr;
            WillAdd.NewCurrPos =
                new PointDef() { X = pFromX + pHeniX * 2, Y = pFromY + pHeniY * 2 };
            WillReturn.Add(WillAdd);
        };

        if (pFromX == 0 && pFromY == 0) { //Aからジャンプする場合
            JumpAct(0, 2);
            JumpAct(1, 1);
            JumpAct(2, 0);
        }
        if (pFromX == 2 && pFromY == 0) { //Bからジャンプする場合
            JumpAct(-1, 1);
            JumpAct(0, 2);
            JumpAct(1, 1);
        }
        if (pFromX == 4 && pFromY == 0) { //Cからジャンプする場合
            JumpAct(-1, 1);
            JumpAct(0, 2);
        }
        if (pFromX == 1 && pFromY == 1) { //Dからジャンプする場合
            JumpAct(1, 1);
        }
        if (pFromX == 3 && pFromY == 1) { //Eからジャンプする場合
            JumpAct(-1, 1);
        }
        if (pFromX == 0 && pFromY == 2) { //Fからジャンプする場合
            JumpAct(1, -1);
            JumpAct(2, 0);
            JumpAct(1, 1);
        }
        if (pFromX == 2 && pFromY == 2) { //Gからジャンプする場合
            JumpAct(-1, -1);
            JumpAct(1, -1);
            JumpAct(-1, 1);
            JumpAct(1, 1);
        }
        if (pFromX == 4 && pFromY == 2) { //Hからジャンプする場合
            JumpAct(-1, -1);
            JumpAct(-2, 0);
            JumpAct(-1, 1);
        }
        if (pFromX == 1 && pFromY == 3) { //Iからジャンプする場合
            JumpAct(1, -1);
        }
        if (pFromX == 3 && pFromY == 3) { //Jからジャンプする場合
            JumpAct(-1, -1);
        }
        if (pFromX == 0 && pFromY == 4) { //Kからジャンプする場合
            JumpAct(0, -2);
            JumpAct(1, -1);
            JumpAct(2, 0);
        }
        if (pFromX == 2 && pFromY == 4) { //Lからジャンプする場合
            JumpAct(-1, -1);
            JumpAct(0, -2);
            JumpAct(1, -1);
        }
        if (pFromX == 4 && pFromY == 4) { //Mからジャンプする場合
            JumpAct(0, -2);
            JumpAct(-1, -1);
            JumpAct(-2, 0);
        }
        return WillReturn.ToArray();
    }

    //カエルがジャンプできるかを判定
    static bool CanJump(char[,] pBanArr, int pFromX, int pFromY, int pHeniX, int pHeniY)
    {
        if (pBanArr[pFromX + pHeniX, pFromY + pHeniY] != '緑') return false;
        if (pBanArr[pFromX + pHeniX * 2, pFromY + pHeniY * 2] != '○') return false;

        return true;
    }

    //盤面を出力
    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());
    }
}


実行結果

3手の解候補を発見
レベル0
緑 ○ ○
 緑 ○ 
○ 緑 ○
 赤 ○ 
○ ○ ○

レベル1
緑 ○ ○
 緑 赤 
○ ○ ○
 ○ ○ 
○ ○ ○

レベル2
○ ○ ○
 ○ 赤 
○ 緑 ○
 ○ ○ 
○ ○ ○

レベル3
○ ○ ○
 ○ ○ 
○ ○ ○
 赤 ○ 
○ ○ ○


解説

変位ベクトルを使って、カエルの移動を表現してます。

Cマガ電脳クラブ(第107回) Hoppers