ABC454-E LRUD Moving

問題へのリンク

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");
            WillReturn.Add("2 1 2");
            WillReturn.Add("3 2 2");
            WillReturn.Add("4 3 2");
            //Yes
            //DR
            //No
            //Yes
            //RRRDLLLDDRRURD
        }
        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 void Main()
    {
        List<string> InputList = GetInputList();

        long[] wkArr = { };
        Action<string> SplitAct = (pStr) => wkArr = GetSplitArr(pStr);

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            mN = wkArr[0];
            mNGY = wkArr[1];
            mNGX = wkArr[2];
            Solve();
        }
    }

    static long mN;
    static long mNGX;
    static long mNGY;

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

        if (mN % 2 == 1) {
            Console.WriteLine("No");
            return;
        }

        if ((mNGX + mNGY) % 2 == 0) {
            Console.WriteLine("No");
            return;
        }

        var AnswerList = new List<char>();
        long CurrY = 1;
        while (true) {
            long CurrPattern = DerivePattern(CurrY);

            if (CurrPattern == 1) AnswerList.AddRange(DerivePattern1List());
            if (CurrPattern == 2) AnswerList.AddRange(DerivePattern2List(CurrY));
            if (CurrPattern == 3) AnswerList.AddRange(DerivePattern3List());

            CurrY += 2;
            if (CurrY > mN) break;
            AnswerList.Add('D');
        }
        Console.WriteLine("Yes");
        var sb = new System.Text.StringBuilder();
        AnswerList.ForEach(pX => sb.Append(pX));
        Console.WriteLine(sb.ToString());
    }

    static long DerivePattern(long pY)
    {
        if (mNGY % 2 == 1) {
            if (mNGY + 1 == pY) return 2;
            if (mNGY == pY) return 2;
        }
        else {
            if (mNGY - 1 == pY) return 2;
            if (mNGY == pY) return 2;
        }

        if (pY < mNGY) return 1;
        return 3;
    }

    static List<char> DerivePattern1List()
    {
        var WillReturn = new List<char>();
        for (long I = 1; I <= mN - 1; I++) {
            WillReturn.Add('R');
        }
        WillReturn.Add('D');
        for (long I = 1; I <= mN - 1; I++) {
            WillReturn.Add('L');
        }
        return WillReturn;
    }

    static List<char> DerivePattern2List(long pStaY)
    {
        var OKYSet = new HashSet<long>() { pStaY, pStaY + 1 };

        var WillReturn = new List<char>();
        long CurrX = 1;
        long CurrY = pStaY;

        var VisitedSet = new HashSet<string>();
        VisitedSet.Add(GetHash(CurrX, CurrY));

        Func<long, long, bool> CanMove = (pNewX, pNewY) =>
        {
            if (OKYSet.Contains(pNewY) == false) return false;
            if (pNewX == mNGX && pNewY == mNGY) return false;

            string Hash = GetHash(pNewX, pNewY);
            return VisitedSet.Add(Hash);
        };

        while (true) {
            if (CurrX == mN && CurrY == OKYSet.Max()) {
                break;
            }

            if (CanMove(CurrX, CurrY - 1)) {
                WillReturn.Add('U');
                CurrY--;
                continue;
            }
            if (CanMove(CurrX, CurrY + 1)) {
                WillReturn.Add('D');
                CurrY++;
                continue;
            }
            if (CanMove(CurrX + 1, CurrY)) {
                WillReturn.Add('R');
                CurrX++;
                continue;
            }
        }
        return WillReturn;
    }

    static string GetHash(long pX, long pY)
    {
        return string.Format("{0},{1}", pX, pY);
    }

    // 変位ベクトルを引数とし、移動の文字を返す
    static char DeriveChar(long pVectX, long pVectY)
    {
        if (pVectX == -1) return 'L';
        if (pVectX == +1) return 'R';
        if (pVectY == -1) return 'U';
        if (pVectY == +1) return 'D';
        throw new Exception("例外発生");
    }

    static List<char> DerivePattern3List()
    {
        var WillReturn = new List<char>();
        for (long I = 1; I <= mN - 1; I++) {
            WillReturn.Add('L');
        }
        WillReturn.Add('D');
        for (long I = 1; I <= mN - 1; I++) {
            WillReturn.Add('R');
        }
        return WillReturn;
    }
}

解説

チェス盤で考察します。

□■□■□■□■
■□■□■□■□
□■□■□■□■
■□■□■□■□
□■□■□■□■
■□■□■□■□
□■□■□■□■
■□■□■□■□

まず、奇数マスだと解なしだと分かります。
たとえば、5マスの場合
5*5-2 = 23
で23は奇数で、
スタートマスとゴールマスは、同じ色であるので
奇数回の4近傍への移動ゴールは不可だと分かります。

また、パリティを使って考えると、
白マスがNGマスだと、解なしであることも分かります。

移動経路の構築ですが、
2マスごとのグループに区切って考えます。

すると、以下のように、NGのマスのY座標との位置関係で場合分けし、
移動方法を変更すれば良いと分かります。

Group1 →→→→→→→↓
Group1 ↓←←←←←←←
Group2 →→→→→→→↓
Group2 ↓←←←←←←←
Group3 ↓→↓×→↓→↓
Group3 →↑→→↑→↑↓
Group4 ↓←←←←←←←
Group4 →→→→→→→↓

補足すると、NGマスと同じグループの場合は、
上下マスが未訪問なら、訪問
上下マスが訪問済なら、右に移動
という貪欲法になります。