ABC184-C Super Ryuma

問題へのリンク

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

    static void Main()
    {
        List<string> InputList = GetInputList();

        int[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(pX => int.Parse(pX)).ToArray();

        SplitAct(InputList[0]);
        int r1 = wkArr[0], c1 = wkArr[1];
        SplitAct(InputList[1]);
        int r2 = wkArr[0], c2 = wkArr[1];

        // 0手の場合
        if (r1 == r2 && c1 == c2) {
            Console.WriteLine(0);
            return;
        }

        // 1手の場合 (ビショップ移動を1回)
        if (CanMoveBishop(r1, c1, r2, c2)) {
            Console.WriteLine(1);
            return;
        }

        // 1手の場合 (ビショップでない移動を1回)
        // 座標を引数とし、ビショップでない移動で、遷移できる座標のListを返す
        List<PointDef> CanMoveNonBishopList1 = DeriveCanMoveNonBishopList(r1, c1);
        if (CanMoveNonBishopList1.Exists(pX => pX.X == r2 && pX.Y == c2)) {
            Console.WriteLine(1);
            return;
        }

        // 2手の場合 (ビショップ移動を2回)
        int Distance = DeriveDistance(r1, c1, r2, c2);
        if (Distance % 2 == 0) {
            Console.WriteLine(2);
            return;
        }

        // 2手の場合 (ビショップでない移動後に、ビショップ移動かビショップでない移動)
        foreach (PointDef EachPoint in CanMoveNonBishopList1) {
            // ビショップ移動
            if (CanMoveBishop(EachPoint.X, EachPoint.Y, r2, c2)) {
                Console.WriteLine(2);
                return;
            }

            //ビショップでない移動
            List<PointDef> CanMoveNonBishopList2 =
                DeriveCanMoveNonBishopList(EachPoint.X, EachPoint.Y);

            if (CanMoveNonBishopList2.Exists(pX => pX.X == r2 && pX.Y == c2)) {
                Console.WriteLine(2);
                return;
            }
        }

        Console.WriteLine(3);
    }

    // 座標2つを引数とし、1手のビショップ移動で到達できるかを返す
    static bool CanMoveBishop(int pX1, int pY1, int pX2, int pY2)
    {
        if (pX1 == pX2 && pY1 == pY2) return false;

        int XDiff = pX2 - pX1;
        int YDiff = pY2 - pY1;

        // 傾きが1か-1ならOK
        if (XDiff == YDiff) return true;
        if (XDiff == -YDiff) return true;

        return false;
    }

    struct PointDef
    {
        internal int X;
        internal int Y;
    }

    // 座標を引数とし、ビショップでない移動で、遷移できる座標のListを返す
    static List<PointDef> DeriveCanMoveNonBishopList(int pX, int pY)
    {
        var WillReturn = new List<PointDef>();

        for (int LoopX = pX - 3; LoopX <= pX + 3; LoopX++) {
            for (int LoopY = pY - 3; LoopY <= pY + 3; LoopY++) {
                int Distance = DeriveDistance(LoopX, LoopY, pX, pY);
                if (1 <= Distance && Distance <= 3) {
                    PointDef WillAdd;
                    WillAdd.X = LoopX;
                    WillAdd.Y = LoopY;
                    WillReturn.Add(WillAdd);
                }
            }
        }
        return WillReturn;
    }

    // 座標2つを引数として、マンハッタン距離を返す
    static int DeriveDistance(int pX1, int pY1, int pX2, int pY2)
    {
        int Distance = 0; // マンハッタン距離
        Distance += Math.Abs(pX1 - pX2);
        Distance += Math.Abs(pY1 - pY2);
        return Distance;
    }
}

解説

最大でも3手なので、0手と1手と2手を調べます。

1手の場合は、下記の2通り
●ビショップ移動
●ビショップでない移動

2手の場合は、下記の3通り
●ビショップ移動を2回
●ビショップでない移動してからビショップ移動
●ビショップでない移動を2回

1手目にビショップ移動して、2手目にビショップでない移動は、
交換法則が成り立つので
1手目にビショップでない移動して、2手目にビショップ移動
と同じです。