ABC007-C 幅優先探索

問題へのリンク

C#のソース

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

class Program
{
    static string InputPattern = "Input1";

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

        if (InputPattern == "Input1") {
            WillReturn.Add("7 8");
            WillReturn.Add("2 2");
            WillReturn.Add("4 5");
            WillReturn.Add("########");
            WillReturn.Add("#......#");
            WillReturn.Add("#.######");
            WillReturn.Add("#..#...#");
            WillReturn.Add("#..##..#");
            WillReturn.Add("##.....#");
            WillReturn.Add("########");
            //11
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5 8");
            WillReturn.Add("2 2");
            WillReturn.Add("2 4");
            WillReturn.Add("########");
            WillReturn.Add("#.#....#");
            WillReturn.Add("#.###..#");
            WillReturn.Add("#......#");
            WillReturn.Add("########");
            //10
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("50 50");
            WillReturn.Add("2 2");
            WillReturn.Add("49 49");
            WillReturn.Add(new string('#', 50));
            for (int I = 1; I <= 48; I++)
                WillReturn.Add('#' + new string('.', 48) + '#');
            WillReturn.Add(new string('#', 50));
            //94
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

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

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

        SplitAct(InputList[0]);
        int R = wkArr[0], C = wkArr[1];
        SplitAct(InputList[1]);
        int SX = wkArr[1] - 1, SY = wkArr[0] - 1;
        SplitAct(InputList[2]);
        int GX = wkArr[1] - 1, GY = wkArr[0] - 1;

        char[,] CArr = new char[C, R];
        int UB_X = CArr.GetUpperBound(0);
        int UB_Y = CArr.GetUpperBound(1);
        for (int X = 0; X <= UB_X; X++) {
            for (int Y = 0; Y <= UB_Y; Y++) {
                CArr[X, Y] = InputList[Y + 3][X];
            }
        }

        var Que = new Queue<JyoutaiDef>();
        JyoutaiDef WillEnqueue;
        WillEnqueue.CurrX = SX;
        WillEnqueue.CurrY = SY;
        WillEnqueue.Level = 0;
        Que.Enqueue(WillEnqueue);

        var VisitedSet = new HashSet<string>();
        VisitedSet.Add(string.Format("{0},{1}", SX, SY));
        while (Que.Count > 0) {
            JyoutaiDef Dequeued = Que.Dequeue();

            //クリア判定
            if (Dequeued.CurrX == GX && Dequeued.CurrY == GY) {
                Console.WriteLine(Dequeued.Level);
                break;
            }

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

                if (CArr[pNewX, pNewY] == '#') return;

                if (VisitedSet.Add(string.Format("{0},{1}", pNewX, pNewY))) {
                    WillEnqueue.CurrX = pNewX;
                    WillEnqueue.CurrY = pNewY;
                    WillEnqueue.Level = Dequeued.Level + 1;
                    Que.Enqueue(WillEnqueue);
                }
            };
            EnqueSyori(Dequeued.CurrX, Dequeued.CurrY - 1);
            EnqueSyori(Dequeued.CurrX, Dequeued.CurrY + 1);
            EnqueSyori(Dequeued.CurrX - 1, Dequeued.CurrY);
            EnqueSyori(Dequeued.CurrX + 1, Dequeued.CurrY);
        }
    }
}

解説

幅優先探索で解いてます。