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

22-07 Rush Hour

問題

ThinkfunのRush Hourを解きます。







ソース

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

class Program
{
    static int mQuestionNo = 7;
    static char[,] mQuestionArr = new char[UB + 1, UB + 1]; //問題の初期盤面
    static char mRedCar; //赤い車の文字

    const int UB = 5;

    //問題を定義
    static void QuestionDef()
    {
        string[] wkStrArr = null;
        if (mQuestionNo == 1) {
            wkStrArr = new string[] {"ABB□□□",
                                     "A□□C□□",
                                     "ADDC□□",
                                     "E□□C□F",
                                     "EGG□□F",
                                     "□□HHHF"};
            mRedCar = 'D';
        }
        if (mQuestionNo == 2) {
            wkStrArr = new string[] {"AABBCD",
                                     "□□EECD",
                                     "□□FFGD",
                                     "□□H□G□",
                                     "□□H□II",
                                     "□□H□□□"};
            mRedCar = 'F';
        }
        if (mQuestionNo == 3) {
            wkStrArr = new string[] {"A□□BCC",
                                     "A□□BD□",
                                     "□□EED□",
                                     "FFGGDH",
                                     "IJKKKH",
                                     "IJ□□□H"};
            mRedCar = 'E';
        }
        if (mQuestionNo == 4) {
            wkStrArr = new string[] {"AAB□□C",
                                     "DDB□□C",
                                     "EEF□□C",
                                     "GHFIII",
                                     "GH□JKK",
                                     "GLLJMM"};
            mRedCar = 'E';
        }
        if (mQuestionNo == 5) {
            wkStrArr = new string[] {"AAB□□□",
                                     "□□BC□□",
                                     "DDECF□",
                                     "GGEHF□",
                                     "IJJHFK",
                                     "ILLL□K"};
            mRedCar = 'D';
        }
        if (mQuestionNo == 6) {
            wkStrArr = new string[] {"ABBCCD",
                                     "A□EFFD",
                                     "GGEH□□",
                                     "□□□HII",
                                     "JJJHK□",
                                     "LLMMK□"};
            mRedCar = 'G';
        }
        if (mQuestionNo == 7) {
            wkStrArr = new string[] {"AAB□□□",
                                     "CDB□□E",
                                     "CDFFGE",
                                     "CHHHGI",
                                     "□□JKGI",
                                     "□□JKLL"};
            mRedCar = 'F';
        }

        for (int X = 0; X <= UB; X++) {
            for (int Y = 0; Y <= UB; Y++) {
                mQuestionArr[X, Y] = wkStrArr[Y][X];
            }
        }
    }

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

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

        //ピースの配置情報を取得
        DerivePieceHeniListDict();

        //反復深化深さ優先探索で解く
        for (int I = 1; I < int.MaxValue; I++) {
            Console.WriteLine("深さ制限={0}で深さ優先探索を実行中", I);
            if (ExecDFS(I)) break;
        }
    }

    //レベル制限を引数として深さ優先探索を行う
    static bool ExecDFS(int pLevelMax)
    {
        //車のIDの配列
        char[] CarIDArr = mQuestionArr.Cast<char>().Where(A => A != '□').Distinct().ToArray();
        Array.Sort<char>(CarIDArr);

        var Stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.BanArr = mQuestionArr;
        WillPush.Level = 0;
        WillPush.Log = new List<string>();
        WillPush.Log.Add(BanToStr(WillPush.BanArr));
        Stk.Push(WillPush);

        var MinTesuuDict = new Dictionary<string, int>();
        MinTesuuDict.Add(GetHash(WillPush.BanArr), 0);

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

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

            if (IsClear(Popped.BanArr)) {
                if (AnswerLog == null && Popped.Level == AnswerLevel
                 || Popped.Level < AnswerLevel) {
                    FoundAnswer = true;
                    AnswerLog = Popped.Log;
                    AnswerLevel = Popped.Level;
                    Console.WriteLine("{0}手の解を発見", Popped.Level);
                }
                break;
            }

            //レベル制限
            if (pLevelMax <= Popped.Level) continue;

            foreach (char EachCarID in CarIDArr) {
                MoveInfoDef wkMoveInfo = DeriveMoveInfo(EachCarID, Popped.BanArr);

                foreach (PointDef EachHeni in wkMoveInfo.HeniArr) {
                    WillPush.BanArr = (char[,])Popped.BanArr.Clone();

                    //移動後の両端の座標を求める
                    int MovedFromX = wkMoveInfo.FromPos.X + EachHeni.X;
                    int MovedFromY = wkMoveInfo.FromPos.Y + EachHeni.Y;
                    int MovedToX = wkMoveInfo.ToPos.X + EachHeni.X;
                    int MovedToY = wkMoveInfo.ToPos.Y + EachHeni.Y;

                    //空白に変更するループ
                    int StaX = Math.Min(MovedFromX, wkMoveInfo.FromPos.X);
                    int StaY = Math.Min(MovedFromY, wkMoveInfo.FromPos.Y);
                    int EndX = Math.Max(MovedToX, wkMoveInfo.ToPos.X);
                    int EndY = Math.Max(MovedToY, wkMoveInfo.ToPos.Y);
                    for (int X = StaX; X <= EndX; X++) {
                        for (int Y = StaY; Y <= EndY; Y++) {
                            WillPush.BanArr[X, Y] = '□';
                        }
                    }

                    //車IDに変更するループ
                    for (int X = MovedFromX; X <= MovedToX; X++) {
                        for (int Y = MovedFromY; Y <= MovedToY; Y++) {
                            WillPush.BanArr[X, Y] = EachCarID;
                        }
                    }

                    WillPush.Level = Popped.Level + 1;

                    //メモ化探索
                    int MinTesuu;
                    string Hash = GetHash(WillPush.BanArr);
                    if (MinTesuuDict.TryGetValue(Hash, out MinTesuu)) {
                        if (MinTesuu <= WillPush.Level) continue;
                    }
                    MinTesuuDict[Hash] = WillPush.Level;

                    WillPush.Log = new List<string>(Popped.Log);
                    WillPush.Log.Add(BanToStr(WillPush.BanArr));
                    Stk.Push(WillPush);
                }
            }
        }
        if (FoundAnswer) {
            for (int I = 0; I <= AnswerLog.Count - 1; I++) {
                Console.WriteLine("{0}手目", I);
                Console.WriteLine(AnswerLog[I]);
            }
        }
        return FoundAnswer;
    }

    //ピースの配置情報を取得
    static Dictionary<char, List<PointDef>> mPieceHeniListDict = new Dictionary<char, List<PointDef>>();
    static void DerivePieceHeniListDict()
    {
        char[] PieceArr = mQuestionArr.Cast<char>().Where(X => X != '□').Distinct().ToArray();
        Array.Sort(PieceArr);

        foreach (char EachPiece in PieceArr) {
            bool FirstFlag = true;
            PointDef GentenPos = new PointDef() { X = -1, Y = -1 };
            for (int LoopY = 0; LoopY <= UB; LoopY++) {
                for (int LoopX = 0; LoopX <= UB; LoopX++) {
                    if (mQuestionArr[LoopX, LoopY] != EachPiece) continue;

                    if (FirstFlag) {
                        FirstFlag = false;
                        GentenPos.X = LoopX;
                        GentenPos.Y = LoopY;
                        mPieceHeniListDict.Add(EachPiece, new List<PointDef>());
                    }
                    //原点 + 変位ベクトル = カレント座標
                    //を移項
                    PointDef HeniVect;
                    HeniVect.X = LoopX - GentenPos.X;
                    HeniVect.Y = LoopY - GentenPos.Y;
                    mPieceHeniListDict[EachPiece].Add(HeniVect);
                }
            }
        }
    }

    //クリア判定
    static bool IsClear(char[,] pBanArr)
    {
        return pBanArr[4, 2] == mRedCar && pBanArr[5, 2] == mRedCar;
    }

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

    //車の移動情報
    struct MoveInfoDef
    {
        internal PointDef FromPos;   //両端の開始座標
        internal PointDef ToPos;     //両端の終了座標
        internal PointDef[] HeniArr; //移動変位の配列
    }

    //車のIDを引数として、車の移動情報を返す
    static MoveInfoDef DeriveMoveInfo(char pCarID, char[,] pBanArr)
    {
        MoveInfoDef MoveInfo = new MoveInfoDef();
        bool CanMoveYoko = DeriveCanMoveYoko(pCarID);

        bool WillBreak = false;
        for (int LoopX = 0; LoopX <= UB; LoopX++) {
            for (int LoopY = 0; LoopY <= UB; LoopY++) {
                if (pBanArr[LoopX, LoopY] != pCarID) continue;

                MoveInfo.FromPos = new PointDef() { X = LoopX, Y = LoopY };
                int CarLength = DeriveCarLength(pCarID);
                if (CanMoveYoko)
                    MoveInfo.ToPos = new PointDef() { X = LoopX + CarLength - 1, Y = LoopY };
                else MoveInfo.ToPos = new PointDef() { X = LoopX, Y = LoopY + CarLength - 1 };
                WillBreak = true;
                break;
            }
            if (WillBreak) break;
        }

        var HeniList = new List<PointDef>();

        Func<int, int, bool> AddFunc = (pI, pBasePos) =>
        {
            if (pBasePos + pI > UB) return false;
            if (pBasePos + pI < 0) return false;

            if (CanMoveYoko) {
                if (pBanArr[pBasePos + pI, MoveInfo.FromPos.Y] != '□') return false;
                HeniList.Add(new PointDef() { X = pI, Y = 0 });
            }
            else {
                if (pBanArr[MoveInfo.FromPos.X, pBasePos + pI] != '□') return false;
                HeniList.Add(new PointDef() { X = 0, Y = pI });
            }
            return true;
        };

        //変位が正の場合
        for (int I = 1; I <= UB; I++) {
            if (AddFunc(I, CanMoveYoko ? MoveInfo.ToPos.X : MoveInfo.ToPos.Y) == false)
                break;
        }

        //変位が負の場合
        for (int I = -1; I >= -UB; I--) {
            if (AddFunc(I, CanMoveYoko ? MoveInfo.FromPos.X : MoveInfo.FromPos.Y) == false)
                break;
        }

        MoveInfo.HeniArr = HeniList.ToArray();
        return MoveInfo;
    }

    //車が横に移動可かを返す
    static bool DeriveCanMoveYoko(char pCarID)
    {
        return mPieceHeniListDict[pCarID][0].X != mPieceHeniListDict[pCarID][1].X;
    }

    //車の長さを返す
    static int DeriveCarLength(char pCarID)
    {
        return mPieceHeniListDict[pCarID].Count;
    }

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

        for (int X = 0; X <= UB; X++) {
            for (int Y = 0; Y <= UB; Y++) {
                char CurrChar = pBanArr[X, Y];

                if (CurrChar == '□') sb.Append(CurrChar);
                else if (AppearedSet.Add(CurrChar)) sb.Append(CurrChar);
            }
        }
        return sb.ToString();
    }

    //盤面をString型で表現
    static string BanToStr(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();
        }
        return sb.ToString();
    }
}


実行結果

深さ制限=1で深さ優先探索を実行中
深さ制限=2で深さ優先探索を実行中
深さ制限=3で深さ優先探索を実行中
3手の解を発見
0手目
ABB□□□
A□□C□□
ADDC□□
E□□C□F
EGG□□F
□□HHHF

1手目
ABB□□□
A□□C□□
ADDC□□
E□□C□F
EGG□□F
HHH□□F

2手目
ABB□□□
A□□□□□
ADD□□□
E□□C□F
EGGC□F
HHHC□F

3手目
ABB□□□
A□□□□□
A□□□DD
E□□C□F
EGGC□F
HHHC□F


解説

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

Cマガ電脳クラブ(第139回) Rush Hour