ABC400-D Takahashi the Wall Breaker

問題へのリンク

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("10 10");
            WillReturn.Add("..........");
            WillReturn.Add("#########.");
            WillReturn.Add("#.......#.");
            WillReturn.Add("#..####.#.");
            WillReturn.Add("##....#.#.");
            WillReturn.Add("#####.#.#.");
            WillReturn.Add(".##.#.#.#.");
            WillReturn.Add("###.#.#.#.");
            WillReturn.Add("###.#.#.#.");
            WillReturn.Add("#.....#...");
            WillReturn.Add("1 1 7 1");
            //1
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2 2");
            WillReturn.Add(".#");
            WillReturn.Add("#.");
            WillReturn.Add("1 1 2 2");
            //1
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("1 3");
            WillReturn.Add(".#.");
            WillReturn.Add("1 1 1 3");
            //1
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("20 20");
            WillReturn.Add("####################");
            WillReturn.Add("##...##....###...###");
            WillReturn.Add("#.....#.....#.....##");
            WillReturn.Add("#..#..#..#..#..#..##");
            WillReturn.Add("#..#..#....##..#####");
            WillReturn.Add("#.....#.....#..#####");
            WillReturn.Add("#.....#..#..#..#..##");
            WillReturn.Add("#..#..#.....#.....##");
            WillReturn.Add("#..#..#....###...###");
            WillReturn.Add("####################");
            WillReturn.Add("####################");
            WillReturn.Add("##..#..##...###...##");
            WillReturn.Add("##..#..#.....#.....#");
            WillReturn.Add("##..#..#..#..#..#..#");
            WillReturn.Add("##..#..#..#..#..#..#");
            WillReturn.Add("##.....#..#..#..#..#");
            WillReturn.Add("###....#..#..#..#..#");
            WillReturn.Add("#####..#.....#.....#");
            WillReturn.Add("#####..##...###...##");
            WillReturn.Add("####################");
            WillReturn.Add("3 3 18 18");
            //3
        }
        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[0]);
        int UB_Y = wkArr[0] - 1;
        int UB_X = wkArr[1] - 1;
        int H = wkArr[0];

        char[,] BanArr = CreateBanArr(InputList.Skip(1).Take(H));
        SplitAct(InputList.Last());
        int StaY = wkArr[0] - 1;
        int StaX = wkArr[1] - 1;
        int GoalY = wkArr[2] - 1;
        int GoalX = wkArr[3] - 1;

        var Que = new LinkedList<JyoutaiDef>();
        JyoutaiDef WillEnqueue;
        WillEnqueue.CurrX = StaX;
        WillEnqueue.CurrY = StaY;
        WillEnqueue.Level = 0;
        Que.AddFirst(WillEnqueue);

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

        while (Que.Count > 0) {
            JyoutaiDef DeQueued = Que.First();
            Que.RemoveFirst();

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

            Func<int, int, bool> IsWall = (pX, pY) =>
            {
                if (pX < 0 || UB_X < pX) return false;
                if (pY < 0 || UB_Y < pY) return false;

                return BanArr[pX, pY] == '#';
            };

            Action<int, int, int> EnqueueAct = (pNewX, pNewY, pCost) =>
            {
                if (pNewX < 0 || UB_X < pNewX) return;
                if (pNewY < 0 || UB_Y < pNewY) return;

                WillEnqueue.CurrX = pNewX;
                WillEnqueue.CurrY = pNewY;
                WillEnqueue.Level = DeQueued.Level + pCost;

                // 枝切り
                long Hash = GetHash(pNewX, pNewY);
                if (EdakiriDict.ContainsKey(Hash)) {
                    if (EdakiriDict[Hash] <= WillEnqueue.Level) {
                        return;
                    }
                }
                EdakiriDict[Hash] = WillEnqueue.Level;

                if (pCost == 0) {
                    Que.AddFirst(WillEnqueue);
                }
                else {
                    Que.AddLast(WillEnqueue);
                }
            };

            for (int I = 1; I <= 4; I++) {
                int VectX = 0;
                int VectY = 0;
                if (I == 1) VectX = +1;
                if (I == 2) VectX = -1;
                if (I == 3) VectY = +1;
                if (I == 4) VectY = -1;

                if (IsWall(CurrX + VectX * 1, CurrY + VectY * 1)) {
                    EnqueueAct(CurrX + VectX * 1, CurrY + VectY * 1, 1);
                    EnqueueAct(CurrX + VectX * 2, CurrY + VectY * 2, 1);
                }
                else {
                    EnqueueAct(CurrX + VectX, CurrY + VectY, 0);
                }
            }
        }
    }

    static long GetHash(int pX, int pY)
    {
        long Hash = 0;
        Hash += pX;
        Hash *= 100000;
        Hash += pY;
        return Hash;
    }

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

    ////////////////////////////////////////////////////////////////
    // IEnumerable<string>をcharの2次元配列に設定
    ////////////////////////////////////////////////////////////////
    static char[,] CreateBanArr(IEnumerable<string> pStrEnum)
    {
        var StrList = pStrEnum.ToList();
        if (StrList.Count == 0) {
            return new char[0, 0];
        }
        int UB_X = StrList[0].Length - 1;
        int UB_Y = StrList.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] = StrList[Y][X];
            }
        }
        return WillReturn;
    }
}

解説

01BFSですが、
実装が悪くても通るように

ノードのHashSetでの再訪防止ではなく
最小コスト[ノード]なDictで枝切りしてます。