第16回PAST K マス目

問題へのリンク

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("SX...");
            WillReturn.Add(".....");
            WillReturn.Add("..GX.");
            WillReturn.Add("..XG.");
            WillReturn.Add("X.X.G");
            //4
            //2
            //-1
            //-1
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2");
            WillReturn.Add("GX");
            WillReturn.Add("XS");
            //-1
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long[] GetSplitArr(string pStr)
    {
        return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
    }

    static long mN;

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

    static long mStaX;
    static long mStaY;

    static long[,] mRunSumArr;

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

        // スタート座標を求める
        for (long X = 0; X <= UB_X; X++) {
            for (long Y = 0; Y <= UB_Y; Y++) {
                if (mBanArr[X, Y] == 'S') {
                    mStaX = X; mStaY = Y;
                }
            }
        }

        // Xの累積和
        mRunSumArr = new long[UB_X + 1, UB_Y + 1];
        for (long LoopX = 0; LoopX <= UB_X; LoopX++) {
            for (long LoopY = 0; LoopY <= UB_Y; LoopY++) {
                if (mBanArr[LoopX, LoopY] == 'X') {
                    mRunSumArr[LoopX, LoopY]++;
                }
            }
        }

        // 累積和を設定する (横方向)
        for (long LoopX = 1; LoopX <= UB_X; LoopX++) {
            for (long LoopY = 0; LoopY <= UB_Y; LoopY++) {
                mRunSumArr[LoopX, LoopY] += mRunSumArr[LoopX - 1, LoopY];
            }
        }

        // 累積和を設定する (縦方向)
        for (long LoopX = 0; LoopX <= UB_X; LoopX++) {
            for (long LoopY = 1; LoopY <= UB_Y; LoopY++) {
                mRunSumArr[LoopX, LoopY] += mRunSumArr[LoopX, LoopY - 1];
            }
        }

        for (long I = 1; I <= mN - 1; I++) {
            long Result = ExecBFS(I);
            Console.WriteLine(Result);
        }
    }

    static long ExecBFS(long pMoveCnt)
    {
        var Que = new Queue<JyoutaiDef>();
        JyoutaiDef WillEnqueue;
        WillEnqueue.CurrX = mStaX;
        WillEnqueue.CurrY = mStaY;
        WillEnqueue.Level = 0;
        Que.Enqueue(WillEnqueue);

        var VisitedSet = new HashSet<long>();

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

            // クリア判定
            if (mBanArr[Dequeued.CurrX, Dequeued.CurrY] == 'G') {
                return Dequeued.Level;
            }

            Action<long, long> EnqueueAct = (long pVectX, long pVectY) =>
            {
                long NewX = Dequeued.CurrX + pVectX * pMoveCnt;
                long NewY = Dequeued.CurrY + pVectY * pMoveCnt;
                if (NewX < 0 || UB_X < NewX) return;
                if (NewY < 0 || UB_Y < NewY) return;

                // 移動経路にXがあったら移動不可
                long MinX = Math.Min(NewX, Dequeued.CurrX);
                long MaxX = Math.Max(NewX, Dequeued.CurrX);
                long MinY = Math.Min(NewY, Dequeued.CurrY);
                long MaxY = Math.Max(NewY, Dequeued.CurrY);

                long SumRect = DeriveSumRect(MinX, MinY, MaxX, MaxY);
                if (SumRect > 0) return;

                if (VisitedSet.Add(GetHash(NewX, NewY))) {
                    WillEnqueue.CurrX = NewX;
                    WillEnqueue.CurrY = NewY;
                    WillEnqueue.Level = Dequeued.Level + 1;
                    Que.Enqueue(WillEnqueue);
                }
            };
            EnqueueAct(0, -1);
            EnqueueAct(0, +1);
            EnqueueAct(-1, 0);
            EnqueueAct(+1, 0);
        }
        return -1;
    }

    static long GetHash(long pX, long pY)
    {
        return pX * 10000 + pY;
    }

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

    // (pStaX,pStaY)と(pEndX,pEndY)からなる矩形の和を求める 
    static long DeriveSumRect(long pStaX, long pStaY, long pEndX, long pEndY)
    {
        long CurrSum = DeriveSumRectZero(pEndX, pEndY);
        CurrSum -= DeriveSumRectZero(pStaX - 1, pEndY);
        CurrSum -= DeriveSumRectZero(pEndX, pStaY - 1);
        CurrSum += DeriveSumRectZero(pStaX - 1, pStaY - 1);
        return CurrSum;
    }

    // (0,0)と(pEndX,pEndY)からなる矩形の和を求める 
    static long DeriveSumRectZero(long pX, long pY)
    {
        if (pX < 0) return 0;
        if (pY < 0) return 0;
        return mRunSumArr[pX, pY];
    }

    ////////////////////////////////////////////////////////////////
    // 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してます。

高速化として、区間内のXの数をO(1)で求めれるように、
最初に二次元累積和を作成してます。

BFSの計算量はO(ノード数 + 枝の数)で
1 + 1/2 + 1/3 + 1/4 ・・・ は、調和級数でO(N(lon(N))なので
全体の計算量は、O(1500*1500 + 1500*1500*2) で O(1500*1500*3) = O(6750000 * log(6750000))
で間に合います。