Q26 効率のよい立体駐車場

C#のソース

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var sw = System.Diagnostics.Stopwatch.StartNew();
        Solve(3, 2);
        Solve(10, 10);
        Console.WriteLine("経過時間={0}", sw.Elapsed);
    }

    static int UB_X;
    static int UB_Y;

    static void Solve(int pX, int pY)
    {
        UB_X = pX - 1;
        UB_Y = pY - 1;
        for (int I = 1; true; I++) {
            if (ExecDFS(I)) break;
        }
    }

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

    //反復深化深さ優先探索で解く
    static bool ExecDFS(int pLimitLevel)
    {
        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.SpaceX = UB_X;
        WillPush.SpaceY = UB_Y;
        WillPush.Level = 0;
        WillPush.BanArr = new char[UB_X + 1, UB_Y + 1];
        for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
            for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
                WillPush.BanArr[LoopX, LoopY] = '○';
            }
        }
        WillPush.BanArr[0, 0] = '●';
        WillPush.BanArr[UB_X, UB_Y] = '空';
        WillPush.BanArrLog = new List<char[,]>() { WillPush.BanArr };
        stk.Push(WillPush);

        //盤面に対する最少手数のDict
        var MinTesuuDict = new Dictionary<string, int>();

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

            //クリア判定
            if (Popped.BanArr[UB_X, UB_Y] == '●') {
                Console.WriteLine("解を発見");
                for (int I = 0; I <= Popped.BanArrLog.Count - 1; I++) {
                    Console.WriteLine("{0}手目", I);
                    PrintBan(Popped.BanArrLog[I]);
                }
                return true;
            }

            //下限値枝切り
            int ManhattanKyori = DeriveManhattanKyori(Popped.BanArr);
            if (Popped.Level + ManhattanKyori > pLimitLevel)
                continue;

            Action<int, int> PushSyori = (pFromX, pFromY) =>
            {
                if (pFromX < 0 || UB_X < pFromX) return;
                if (pFromY < 0 || UB_Y < pFromY) return;

                WillPush.SpaceX = pFromX;
                WillPush.SpaceY = pFromY;
                WillPush.Level = Popped.Level + 1;

                WillPush.BanArr = (char[,])Popped.BanArr.Clone();
                WillPush.BanArr[Popped.SpaceX, Popped.SpaceY] =
                    Popped.BanArr[pFromX, pFromY];
                WillPush.BanArr[pFromX, pFromY] = '空';

                //当該盤面に、少ない手数か等しい手数で、到達済なら枝切り
                string BanStr = BanToStr(WillPush.BanArr);
                int MinTesuu;
                if (MinTesuuDict.TryGetValue(BanStr, out MinTesuu)) {
                    if (MinTesuu <= WillPush.Level) return;
                }
                MinTesuuDict[BanStr] = WillPush.Level;

                WillPush.BanArrLog = new List<char[,]>(Popped.BanArrLog);
                WillPush.BanArrLog.Add(WillPush.BanArr);
                stk.Push(WillPush);
            };
            PushSyori(Popped.SpaceX, Popped.SpaceY - 1);
            PushSyori(Popped.SpaceX, Popped.SpaceY + 1);
            PushSyori(Popped.SpaceX - 1, Popped.SpaceY);
            PushSyori(Popped.SpaceX + 1, Popped.SpaceY);
        }
        return false;
    }

    //ゴールまでのマンハッタン距離を求める
    static int DeriveManhattanKyori(char[,] pBanArr)
    {
        int CurrX = -1, CurrY = -1;
        bool WillBreak = false;

        for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
            for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
                if (pBanArr[LoopX, LoopY] == '●') {
                    CurrX = LoopX;
                    CurrY = LoopY;
                    WillBreak = true;
                    break;
                }
            }
            if (WillBreak) break;
        }
        return UB_X - CurrX + UB_Y - CurrY;
    }

    //盤面をString型で表現
    static string BanToStr(char[,] pBanArr)
    {
        var sb = new System.Text.StringBuilder();
        for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
            for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
                sb.Append(pBanArr[LoopX, LoopY]);
            }
        }
        return sb.ToString();
    }

    //盤面を表示
    static void PrintBan(char[,] pBanArr)
    {
        var sb = new System.Text.StringBuilder();

        for (int Y = 0; Y <= UB_Y; Y++) {
            for (int X = 0; X <= UB_X; X++) {
                sb.Append(pBanArr[X, Y]);
            }
            sb.AppendLine();
        }
        Console.WriteLine(sb.ToString());
    }
}

実行結果

省略
69手目
○○○○○○○○○○
○○○○○○○○○○
○○○○○○○○○○
○○○○○○○○○○
○○○○○○○○○○
○○○○○○○○○○
○○○○○○○○○○
○○○○○○○○○○
○○○○○○○○○○
○○○○○○○○空●

経過時間=00:00:16.3607519

解説

反復深化深さ優先探索と下限値枝切りを組み合わせてます。