ABC308-D Snuke 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("2 3");
            WillReturn.Add("sns");
            WillReturn.Add("euk");
            //Yes
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2 2");
            WillReturn.Add("ab");
            WillReturn.Add("cd");
            //No
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("5 7");
            WillReturn.Add("skunsek");
            WillReturn.Add("nukesnu");
            WillReturn.Add("ukeseku");
            WillReturn.Add("nsnnesn");
            WillReturn.Add("uekukku");
            //Yes
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static char[,] mBanArr;
    static int UB_X;
    static int UB_Y;

    static void Main()
    {
        List<string> InputList = GetInputList();
        mBanArr = CreateBanArr(InputList.Skip(1));
        UB_X = mBanArr.GetUpperBound(0);
        UB_Y = mBanArr.GetUpperBound(1);

        if (mBanArr[0, 0] != 's') {
            Console.WriteLine("No");
            return;
        }
        bool Result = ExecDFS();
        if (Result) {
            Console.WriteLine("Yes");
        }
        else {
            Console.WriteLine("No");
        }
    }

    static bool ExecDFS()
    {
        var Stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.Curr_X = 0;
        WillPush.Curr_Y = 0;
        WillPush.Level = 0;
        Stk.Push(WillPush);

        var VisitedSet = new HashSet<long>();

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

            // クリア判定
            if (Popped.Curr_X == UB_X && Popped.Curr_Y == UB_Y) {
                return true;
            }

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

                WillPush.Curr_X = pNewX;
                WillPush.Curr_Y = pNewY;
                WillPush.Level = Popped.Level + 1;
                WillPush.Level %= 5;

                if (WillPush.Level == 0 && mBanArr[pNewX, pNewY] != 's') return;
                if (WillPush.Level == 1 && mBanArr[pNewX, pNewY] != 'n') return;
                if (WillPush.Level == 2 && mBanArr[pNewX, pNewY] != 'u') return;
                if (WillPush.Level == 3 && mBanArr[pNewX, pNewY] != 'k') return;
                if (WillPush.Level == 4 && mBanArr[pNewX, pNewY] != 'e') return;

                long Hash = GetHash(WillPush);
                if (VisitedSet.Add(Hash)) {
                    Stk.Push(WillPush);
                }
            };
            PushAct(Popped.Curr_X, Popped.Curr_Y - 1);
            PushAct(Popped.Curr_X, Popped.Curr_Y + 1);
            PushAct(Popped.Curr_X - 1, Popped.Curr_Y);
            PushAct(Popped.Curr_X + 1, Popped.Curr_Y);
        }
        return false;
    }

    struct JyoutaiDef
    {
        internal int Curr_X;
        internal int Curr_Y;
        internal int Level;
    }

    static long GetHash(JyoutaiDef pJyoutai)
    {
        long Hash = 0;
        Hash += pJyoutai.Curr_X * 1000;
        Hash += pJyoutai.Curr_Y;
        Hash *= 10;
        Hash += pJyoutai.Level % 5;
        return Hash;
    }

    ////////////////////////////////////////////////////////////////
    // 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;
    }
}

解説

{現在X,現在Y,Level の mod 5} からなるハッシュ値を使って、
再訪防止のDFSを行ってます。