第11回PAST I お片付け

問題へのリンク

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

    static int UB_X;
    static int UB_Y;

    static void Main()
    {
        List<string> InputList = GetInputList();
        char[,] BaseBanArr = CreateBanArr(InputList.Skip(1));
        UB_X = BaseBanArr.GetUpperBound(0);
        UB_Y = BaseBanArr.GetUpperBound(1);

        // 片付け先の座標
        int Goal_X = -1;
        int Goal_Y = -1;

        // すぬけ君の座標
        int S_X = -1;
        int S_Y = -1;

        // 荷物の座標
        int A_X = -1;
        int A_Y = -1;

        for (int X = 0; X <= UB_X; X++) {
            for (int Y = 0; Y <= UB_Y; Y++) {
                if (BaseBanArr[X, Y] == 'g') {
                    BaseBanArr[X, Y] = '.';
                    Goal_X = X;
                    Goal_Y = Y;
                }
                if (BaseBanArr[X, Y] == 'a') {
                    A_X = X;
                    A_Y = Y;
                }
                if (BaseBanArr[X, Y] == 's') {
                    S_X = X;
                    S_Y = Y;
                }
            }
        }

        var Que = new Queue<JyoutaiDef>();
        JyoutaiDef WillEnqueue;
        WillEnqueue.A_X = A_X;
        WillEnqueue.A_Y = A_Y;
        WillEnqueue.S_X = S_X;
        WillEnqueue.S_Y = S_Y;
        WillEnqueue.Level = 0;
        Que.Enqueue(WillEnqueue);

        var VisitedSet = new HashSet<long>();
        VisitedSet.Add(GetHash(WillEnqueue));

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

            // クリア判定
            if (Dequeued.A_X == Goal_X && Dequeued.A_Y == Goal_Y) {
                Console.WriteLine(Dequeued.Level);
                return;
            }

            Action<int, int> EnqueueAct = (pVectX, pVectY) =>
            {
                int NewX = Dequeued.S_X + pVectX;
                int NewY = Dequeued.S_Y + pVectY;

                // 盤外の場合
                if (NewX < 0 || UB_X < NewX) return;
                if (NewY < 0 || UB_Y < NewY) return;

                // 壁の場合
                if (BaseBanArr[NewX, NewY] == '#') return;

                // 空きマスの場合
                if (NewX != Dequeued.A_X || NewY != Dequeued.A_Y) {
                    WillEnqueue.A_X = Dequeued.A_X;
                    WillEnqueue.A_Y = Dequeued.A_Y;
                    WillEnqueue.S_X = NewX;
                    WillEnqueue.S_Y = NewY;
                    long Hash = GetHash(WillEnqueue);
                    if (VisitedSet.Add(Hash)) {
                        WillEnqueue.Level = Dequeued.Level + 1;
                        Que.Enqueue(WillEnqueue);
                    }
                }

                // 荷物がある場合
                if (NewX == Dequeued.A_X && NewY == Dequeued.A_Y) {
                    int NewX2 = Dequeued.S_X + pVectX * 2;
                    int NewY2 = Dequeued.S_Y + pVectY * 2;

                    // 盤外の場合
                    if (NewX2 < 0 || UB_X < NewX2) return;
                    if (NewY2 < 0 || UB_Y < NewY2) return;

                    // 壁の場合
                    if (BaseBanArr[NewX2, NewY2] == '#') return;

                    WillEnqueue.S_X = NewX;
                    WillEnqueue.S_Y = NewY;
                    WillEnqueue.A_X = NewX2;
                    WillEnqueue.A_Y = NewY2;
                    long Hash = GetHash(WillEnqueue);
                    if (VisitedSet.Add(Hash)) {
                        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 A_X;
        internal int A_Y;
        internal int S_X;
        internal int S_Y;
        internal int Level;
    }

    // 盤面のハッシュ値を求める
    static long GetHash(JyoutaiDef pJyoutai)
    {
        long A_X = pJyoutai.A_X;
        long A_Y = pJyoutai.A_Y;
        long S_X = pJyoutai.S_X;
        long S_Y = pJyoutai.S_Y;

        long Hash = 0;
        Hash += A_X * 1000000000;
        Hash += A_Y * 1000000;
        Hash += S_X * 1000;
        Hash += S_Y;
        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;
    }
}

解説

BFSで解いてます。
二次元配列を状態に持つと、定数倍が重すぎてTLEするので
すぬけ君の座標と荷物の座標のみを状態に持ってます。