トップページに戻る    次の増井さんの書籍の問題へ    前の増井さんの書籍の問題へ

Q64 迷路で待ち合わせ


C#のソース

using System;
using System.Collections.Generic;

class Program
{
    const int UB = 5 - 1;

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

    static void Main()
    {
        var sw = System.Diagnostics.Stopwatch.StartNew();

        int AnswerCnt = 0;
        foreach (bool[,] EachMeiroArr in DeriveMeiroArrEnum()) {
            PointDef[] VisitedPointArr1 =
                DeriveVisitedPointArr(EachMeiroArr,
                                      new PointDef() { X = 0, Y = 0 },
                                      new PointDef() { X = UB, Y = UB },
                                      new PointDef() { X = 0, Y = 1 });
            PointDef[] VisitedPointArr2 =
                DeriveVisitedPointArr(EachMeiroArr,
                                      new PointDef() { X = UB, Y = UB },
                                      new PointDef() { X = 0, Y = 0 },
                                      new PointDef() { X = 0, Y = -1 });

            for (int I = 0; I <= Math.Min(VisitedPointArr1.GetUpperBound(0),
                                          VisitedPointArr2.GetUpperBound(0)); I++) {
                if (VisitedPointArr1[I].X == VisitedPointArr2[I].X
                 && VisitedPointArr1[I].Y == VisitedPointArr2[I].Y) {
                    AnswerCnt++;
                    if (AnswerCnt % 100000 == 0) {
                        Console.WriteLine("{0}個目の解を発見。経過時間={1}", AnswerCnt, sw.Elapsed);
                    }
                    break;
                }
                if (VisitedPointArr1[I].X == UB && VisitedPointArr1[I].Y == UB)
                    break;
                if (VisitedPointArr2[I].X == 0 && VisitedPointArr2[I].Y == 0)
                    break;
            }
        }
        Console.WriteLine("解は{0}通り。経過時間={1}", AnswerCnt, sw.Elapsed);
    }

    struct JyoutaiDefDFS
    {
        internal int CurrX;
        internal int CurrY;
        internal bool[,] BanArr;
    }

    //迷路を列挙
    static IEnumerable<bool[,]> DeriveMeiroArrEnum()
    {
        var stk = new Stack<JyoutaiDefDFS>();
        JyoutaiDefDFS WillPush;
        //[0,0]に壁は配置できない
        WillPush.CurrX = 1;
        WillPush.CurrY = 0;
        WillPush.BanArr = new bool[UB + 1, UB + 1];
        stk.Push(WillPush);

        while (stk.Count > 0) {
            JyoutaiDefDFS Popped = stk.Pop();

            //クリア判定
            if (Popped.CurrX == UB && Popped.CurrY == UB) {
                yield return Popped.BanArr;
                continue;
            }

            //X座標の繰上げ処理
            if (Popped.CurrX > UB) {
                Popped.CurrX = 0;
                Popped.CurrY++;
            }

            //壁を配置する経路
            WillPush.CurrX = Popped.CurrX + 1;
            WillPush.CurrY = Popped.CurrY;
            WillPush.BanArr = (bool[,])Popped.BanArr.Clone();
            WillPush.BanArr[Popped.CurrX, Popped.CurrY] = true;
            //ゴールに到着可能な迷路かを、UnionFindで判定
            if (IsValidMeiro(WillPush.BanArr)) {
                stk.Push(WillPush);
            }

            //壁を配置しない経路
            WillPush.CurrX = Popped.CurrX + 1;
            WillPush.CurrY = Popped.CurrY;
            WillPush.BanArr = Popped.BanArr;
            stk.Push(WillPush);
        }
    }

    struct JyoutaiDefUnionFind
    {
        internal int CurrX;
        internal int CurrY;
    }

    //ゴールに到着可能な迷路かを、UnionFindで判定
    static bool IsValidMeiro(bool[,] pBanArr)
    {
        var stk = new Stack<JyoutaiDefUnionFind>();
        JyoutaiDefUnionFind WillPush;
        WillPush.CurrX = 0;
        WillPush.CurrY = 0;
        stk.Push(WillPush);

        var VisitedSet = new HashSet<string>();
        while (stk.Count > 0) {
            JyoutaiDefUnionFind Popped = stk.Pop();

            //クリア判定
            if (VisitedSet.Contains(string.Format("({0},{1})", UB, UB))) {
                return true;
            }

            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)) {
                    WillPush.CurrX = pNewX;
                    WillPush.CurrY = pNewY;
                    stk.Push(WillPush);
                }
            };
            PushSyori(Popped.CurrX, Popped.CurrY - 1);
            PushSyori(Popped.CurrX, Popped.CurrY + 1);
            PushSyori(Popped.CurrX - 1, Popped.CurrY);
            PushSyori(Popped.CurrX + 1, Popped.CurrY);
        }
        return false;
    }

    //迷路と開始座標と終了座標と変位ベクトルを引数とし、右手法での訪問座標の配列を返す
    static PointDef[] DeriveVisitedPointArr(bool[,] pBanArr,
        PointDef pStaPos, PointDef pGoalPos, PointDef pHeniVect)
    {
        var WillReturn = new List<PointDef>();
        WillReturn.Add(new PointDef() { X = pStaPos.X, Y = pStaPos.Y });

        PointDef CurrPos = pStaPos;
        PointDef CurrHeniVect = pHeniVect;

        while (true) {
            PointDef SakiPos = CurrPos;
            SakiPos.X += CurrHeniVect.X;
            SakiPos.Y += CurrHeniVect.Y;
            //進行先が空なら移動する
            if (IsWall(pBanArr, SakiPos) == false) {
                CurrPos = SakiPos;
            }
            else { //進行先が壁の場合
                //進行先の左が空の場合、向きを左にして進む
                PointDef HidariPos = CurrPos;
                PointDef HidariVect = KaitenHidari90Do(CurrHeniVect);
                HidariPos.X += HidariVect.X;
                HidariPos.Y += HidariVect.Y;
                if (IsWall(pBanArr, HidariPos) == false) {
                    CurrPos = HidariPos;
                    CurrHeniVect = HidariVect;
                }
                else { //進行先の左が壁の場合、向きを反転して進む
                    CurrHeniVect = KaitenHidari90Do(HidariVect);
                    CurrPos.X += CurrHeniVect.X;
                    CurrPos.Y += CurrHeniVect.Y;
                }
            }
            //進行方向の右側が空いてたら、変位ベクトルを右に90度回転
            PointDef MigiPos = CurrPos;
            PointDef MigiVect = KaitenMigi90Do(CurrHeniVect);
            MigiPos.X += MigiVect.X;
            MigiPos.Y += MigiVect.Y;
            if (IsWall(pBanArr, MigiPos) == false) {
                CurrHeniVect = MigiVect;
            }

            WillReturn.Add(new PointDef() { X = CurrPos.X, Y = CurrPos.Y });
            if (CurrPos.X == pGoalPos.X && CurrPos.Y == pGoalPos.Y)
                break;
        }
        return WillReturn.ToArray();
    }

    //右に90度回転させた変位ベクトルを返す
    static PointDef KaitenMigi90Do(PointDef pBaseVect)
    {
        int X = pBaseVect.X;
        int Y = pBaseVect.Y;
        if (X == 0 && Y == -1) return new PointDef() { X = 1, Y = 0 };
        if (X == 0 && Y == 1) return new PointDef() { X = -1, Y = 0 };
        if (X == -1 && Y == 0) return new PointDef() { X = 0, Y = -1 };
        return new PointDef() { X = 0, Y = 1 };
    }

    //左に90度回転させた変位ベクトルを返す
    static PointDef KaitenHidari90Do(PointDef pBaseVect)
    {
        int X = pBaseVect.X;
        int Y = pBaseVect.Y;
        if (X == 0 && Y == -1) return new PointDef() { X = -1, Y = 0 };
        if (X == 0 && Y == 1) return new PointDef() { X = 1, Y = 0 };
        if (X == -1 && Y == 0) return new PointDef() { X = 0, Y = 1 };
        return new PointDef() { X = 0, Y = -1 };
    }

    //座標を引数として、壁かを判定
    static bool IsWall(bool[,] pBanArr, PointDef pTargetPoint)
    {
        int X = pTargetPoint.X;
        int Y = pTargetPoint.Y;
        if (X < 0 || pBanArr.GetUpperBound(0) < X) return true;
        if (Y < 0 || pBanArr.GetUpperBound(1) < Y) return true;

        return pBanArr[X, Y];
    }
}


実行結果

100000個目の解を発見。経過時間=00:00:30.6275163
200000個目の解を発見。経過時間=00:00:57.7332923
300000個目の解を発見。経過時間=00:01:22.1262825
400000個目の解を発見。経過時間=00:01:52.8526888
500000個目の解を発見。経過時間=00:02:21.7528194
600000個目の解を発見。経過時間=00:02:47.1543662
解は660148通り。経過時間=00:03:01.3036539


解説

右手法での探索の実装が難しかったです。