ABC339-D Synchronized Players

問題へのリンク

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("5");
            WillReturn.Add("....#");
            WillReturn.Add("#..#.");
            WillReturn.Add(".P...");
            WillReturn.Add("..P..");
            WillReturn.Add("....#");
            //3
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2");
            WillReturn.Add("P#");
            WillReturn.Add("#P");
            //-1
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("10");
            WillReturn.Add("..........");
            WillReturn.Add("..........");
            WillReturn.Add("..........");
            WillReturn.Add("..........");
            WillReturn.Add("....P.....");
            WillReturn.Add(".....P....");
            WillReturn.Add("..........");
            WillReturn.Add("..........");
            WillReturn.Add("..........");
            WillReturn.Add("..........");
            //10
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static int UB;
    static char[,] mBanArr;

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

        var Que = new Queue<JyoutaiDef>();
        JyoutaiDef WillEnqueue;
        WillEnqueue.CurrX1 = 0;
        WillEnqueue.CurrY1 = 0;
        WillEnqueue.CurrX2 = 0;
        WillEnqueue.CurrY2 = 0;
        WillEnqueue.Level = 0;

        int PCnt = 0;
        for (int X = 0; X <= UB; X++) {
            for (int Y = 0; Y <= UB; Y++) {
                if (mBanArr[X, Y] == 'P') {
                    if (PCnt == 0) {
                        PCnt++;
                        WillEnqueue.CurrX1 = X;
                        WillEnqueue.CurrY1 = Y;
                    }
                    else {
                        WillEnqueue.CurrX2 = X;
                        WillEnqueue.CurrY2 = Y;
                        Que.Enqueue(WillEnqueue);
                    }
                }
            }
        }

        var VisitedSet = new HashSet<long>();

        while (Que.Count > 0) {
            JyoutaiDef Dequeued = Que.Dequeue();

            if (Dequeued.CurrX1 == Dequeued.CurrX2 && Dequeued.CurrY1 == Dequeued.CurrY2) {
                Console.WriteLine(Dequeued.Level);
                return;
            }

            Action<int, int> EnqueueAct = (pVectX, pVectY) =>
            {
                int NewX1 = Dequeued.CurrX1 + pVectX;
                int NewX2 = Dequeued.CurrX2 + pVectX;
                int NewY1 = Dequeued.CurrY1 + pVectY;
                int NewY2 = Dequeued.CurrY2 + pVectY;

                bool Cancel1 = false;
                if (NewX1 < 0 || UB < NewX1) Cancel1 = true;
                else if (NewY1 < 0 || UB < NewY1) Cancel1 = true;
                else if (mBanArr[NewX1, NewY1] == '#') Cancel1 = true;
                if (Cancel1) {
                    NewX1 = Dequeued.CurrX1;
                    NewY1 = Dequeued.CurrY1;
                }

                bool Cancel2 = false;
                if (NewX2 < 0 || UB < NewX2) Cancel2 = true;
                else if (NewY2 < 0 || UB < NewY2) Cancel2 = true;
                else if (mBanArr[NewX2, NewY2] == '#') Cancel2 = true;
                if (Cancel2) {
                    NewX2 = Dequeued.CurrX2;
                    NewY2 = Dequeued.CurrY2;
                }

                long Hash = GetHash(NewX1, NewY1, NewX2, NewY2);
                if (VisitedSet.Add(Hash)) {
                    WillEnqueue.CurrX1 = NewX1;
                    WillEnqueue.CurrY1 = NewY1;
                    WillEnqueue.CurrX2 = NewX2;
                    WillEnqueue.CurrY2 = NewY2;
                    WillEnqueue.Level = Dequeued.Level + 1;
                    Que.Enqueue(WillEnqueue);
                }
            };

            EnqueueAct(0, -1);
            EnqueueAct(0, 1);
            EnqueueAct(-1, 0);
            EnqueueAct(1, 0);
        }
        Console.WriteLine(-1);
    }

    struct JyoutaiDef
    {
        internal int CurrX1;
        internal int CurrY1;
        internal int CurrX2;
        internal int CurrY2;
        internal int Level;
    }

    static long GetHash(long p1, long p2, long p3, long p4)
    {
        long WillReturn = 0;
        WillReturn += p4; WillReturn *= 100;
        WillReturn += p3; WillReturn *= 100;
        WillReturn += p2; WillReturn *= 100;
        WillReturn += p1;
        return WillReturn;
    }

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

解説

BFSで解いてます。
コンテストでは、2回も誤読したので、誤読した原因を調べておく。
コンテストでは、2回も誤読したので、誤読した原因を調べておく。
コンテストでは、2回も誤読したので、誤読した原因を調べておく。
コンテストでは、2回も誤読したので、誤読した原因を調べておく。
コンテストでは、2回も誤読したので、誤読した原因を調べておく。