ABC176-D Wizard in Maze

問題へのリンク

C#のソース

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

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("4 4");
            WillReturn.Add("1 1");
            WillReturn.Add("4 4");
            WillReturn.Add("..#.");
            WillReturn.Add("..#.");
            WillReturn.Add(".#..");
            WillReturn.Add(".#..");
            //1
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4 4");
            WillReturn.Add("1 4");
            WillReturn.Add("4 1");
            WillReturn.Add(".##.");
            WillReturn.Add("####");
            WillReturn.Add("####");
            WillReturn.Add(".##.");
            //-1
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("4 4");
            WillReturn.Add("2 2");
            WillReturn.Add("3 3");
            WillReturn.Add("....");
            WillReturn.Add("....");
            WillReturn.Add("....");
            WillReturn.Add("....");
            //0
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("4 5");
            WillReturn.Add("1 2");
            WillReturn.Add("2 5");
            WillReturn.Add("#.###");
            WillReturn.Add("####.");
            WillReturn.Add("#..##");
            WillReturn.Add("#..##");
            //2
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();

        int[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(pX => int.Parse(pX)).ToArray();

        SplitAct(InputList[1]);
        int StaX = wkArr[1] - 1;
        int StaY = wkArr[0] - 1;

        SplitAct(InputList[2]);
        int GoalX = wkArr[1] - 1;
        int GoalY = wkArr[0] - 1;

        char[,] BanArr = CreateBanArr(InputList.Skip(3).ToList());
        int UB_X = BanArr.GetUpperBound(0);
        int UB_Y = BanArr.GetUpperBound(1);

        var Que0 = new Queue<JyoutaiDef>();
        var Que1 = new Queue<JyoutaiDef>();
        JyoutaiDef WillEnqueue;
        WillEnqueue.Level = 0;
        WillEnqueue.CurrX = StaX;
        WillEnqueue.CurrY = StaY;
        Que0.Enqueue(WillEnqueue);

        var MinLevelDict = new Dictionary<long, int>();

        while (Que0.Count > 0 || Que1.Count > 0) {
            JyoutaiDef Dequeued;
            if (Que0.Count > 0) {
                Dequeued = Que0.Dequeue();
            }
            else {
                Dequeued = Que1.Dequeue();
            }

            long Hash = Dequeued.CurrX * 10000 + Dequeued.CurrY;

            // 下限値枝切り
            if (MinLevelDict.ContainsKey(Hash)) {
                if (MinLevelDict[Hash] <= Dequeued.Level) {
                    continue;
                }
            }
            MinLevelDict[Hash] = Dequeued.Level;

            if (Dequeued.CurrX == GoalX && Dequeued.CurrY == GoalY) {
                Console.WriteLine(Dequeued.Level);
                return;
            }

            Action<int, int, int, bool> EnqueueAct = (pNewX, pNewY, pNewLevel, pEnqueue0) =>
            {
                if (pNewX < 0 || UB_X < pNewX) return;
                if (pNewY < 0 || UB_Y < pNewY) return;
                if (BanArr[pNewX, pNewY] == '#') return;

                WillEnqueue.Level = pNewLevel;
                WillEnqueue.CurrX = pNewX;
                WillEnqueue.CurrY = pNewY;
                if (pEnqueue0) {
                    Que0.Enqueue(WillEnqueue);
                }
                else {
                    Que1.Enqueue(WillEnqueue);
                }
            };

            // 4近傍に移動
            EnqueueAct(Dequeued.CurrX, Dequeued.CurrY - 1, Dequeued.Level, true);
            EnqueueAct(Dequeued.CurrX, Dequeued.CurrY + 1, Dequeued.Level, true);
            EnqueueAct(Dequeued.CurrX - 1, Dequeued.CurrY, Dequeued.Level, true);
            EnqueueAct(Dequeued.CurrX + 1, Dequeued.CurrY, Dequeued.Level, true);

            // 5*5の範囲でワープ
            for (int LoopX = Dequeued.CurrX - 2; LoopX <= Dequeued.CurrX + 2; LoopX++) {
                for (int LoopY = Dequeued.CurrY - 2; LoopY <= Dequeued.CurrY + 2; LoopY++) {
                    EnqueueAct(LoopX, LoopY, Dequeued.Level + 1, false);
                }
            }
        }
        Console.WriteLine(-1);
    }

    struct JyoutaiDef
    {
        internal int Level;
        internal int CurrX;
        internal int CurrY;
    }

    // stringのListをcharの2次元配列に設定する
    static char[,] CreateBanArr(List<string> pStringList)
    {
        if (pStringList.Count == 0) {
            return new char[0, 0];
        }
        int UB_X = pStringList[0].Length - 1;
        int UB_Y = pStringList.Count - 1;

        char[,] WillReturn = new char[UB_X + 1, UB_Y + 1];

        for (int Y = 0; Y <= UB_Y; Y++) {
            for (int X = 0; X <= UB_X; X++) {
                WillReturn[X, Y] = pStringList[Y][X];
            }
        }
        return WillReturn;
    }

    // 2次元配列のデバッグ出力
    static void PrintBan(char[,] pBanArr)
    {
        for (int Y = 0; Y <= pBanArr.GetUpperBound(1); Y++) {
            for (int X = 0; X <= pBanArr.GetUpperBound(0); X++) {
                Console.Write(pBanArr[X, Y]);
            }
            Console.WriteLine();
        }
    }
}

解説

徒歩による移動をコスト0
ワープによる移動をコスト1
とした01BFSで解いてます。