ABC-051-C Back and Forth

■■■問題■■■

イルカはx軸正方向を右、y軸正方向を上とする2次元座標平面にいます。

イルカは現在点 (sx,sy) にいて、1秒あたり上下左右に距離1だけ進むことができます。
このとき、移動前と移動後のx座標、y座標はともに整数でなければなりません。

イルカはここから sx<tx と sy<ty を満たす点 (tx,ty) に行き、
その後点 (sx,sy) に戻り、また点 (tx,ty) に行き、その後点 (sx,sy) に戻ります。

このとき、イルカは点 (sx,sy) と点 (tx,ty) を除いて、
途中で同じ座標を複数回通らないように移動しなければなりません。
このような条件を満たすイルカの最短経路を1つ求めてください。 

■■■入力■■■

sx sy tx ty

●-1000 <= sx < tx <= 1000
●-1000 <= sy < ty <= 1000
●sx,sy,tx,ty は整数である

■■■出力■■■

イルカの最短経路を表す文字列Sを出力せよ。
Sのi番目の文字はイルカのi番目の移動を表す。

イルカの各方向への移動を表す文字の対応関係は以下のとおりである。
●U: 上方向
●D: 下方向
●L: 左方向
●R: 右方向
条件を満たすような最短経路が複数ある場合、そのうちどれか1つを出力せよ。

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("0 0 1 2");
            //UURDDLLUUURRDRDDDLLU
            //以下に示す移動経路が最短経路の1つです。 
            //●1回目の (sx,sy) から (tx,ty) への移動: 
            //          (0,0)→(0,1)→(0,2)→(1,2)
            //●1回目の (tx,ty) から (sx,sy) への移動:
            //          (1,2)→(1,1)→(1,0)→(0,0)
            //●2回目の (sx,sy) から (tx,ty) への移動:
            //          (0,0)→(-1,0)→(-1,1)→(-1,2)→(-1,3)→(0,3)→(1,3)→(1,2)
            //●2回目の (tx,ty) から (sx,sy) への移動:
            //          (1,2)→(2,2)→(2,1)→(2,0)→(2,-1)→(1,-1)→(0,-1)→(0,0)
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("-2 -2 1 1");
            //UURRURRDDDLLDLLULUUURRURRDDDLLDL
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int[] wkArr = InputList[0].Split(' ').Select(X => int.Parse(X)).ToArray();

        int SX = wkArr[0];
        int SY = wkArr[1];
        int TX = wkArr[2];
        int TY = wkArr[3];

        //1回目と2回目の移動
        var sb = new System.Text.StringBuilder();
        for (int I = 1; I <= TX - SX; I++) sb.Append('R');
        for (int I = 1; I <= TY - SY; I++) sb.Append('U');
        string wkStr1 = sb.ToString();
        Console.Write(wkStr1);
        Console.Write(DeriveRevStr(wkStr1));

        //3回目と4回目の移動
        sb.Length = 0;
        sb.Append('D');
        for (int I = 1; I <= TX - SX + 1; I++) sb.Append('R');
        for (int I = 1; I <= TY - SY + 1; I++) sb.Append('U');
        sb.Append('L');
        string wkStr2 = sb.ToString();
        Console.Write(wkStr2);
        Console.Write(DeriveRevStr(wkStr2));
        Console.WriteLine();
    }

    //対称をなす移動経路を返す
    static string DeriveRevStr(string pStr)
    {
        var sb = new System.Text.StringBuilder();
        foreach (char EachChar in pStr) {
            if (EachChar == 'R') sb.Append('L');
            if (EachChar == 'L') sb.Append('R');
            if (EachChar == 'U') sb.Append('D');
            if (EachChar == 'D') sb.Append('U');
        }
        return sb.ToString();
    }
}

解説

始点の4近傍のどれを通るかが決まれば、
終点の4近傍のどれを通るかも決まることを利用してます。