No.367 ナイトの転身

■■■問題■■■

あなたはチェスの駒を用いたゲームに取り組んでいます。
このゲームは、H行W列のチェス盤上で、
駒をスタート地点のマスからゴール地点のマスまで移動させるとクリアとなります。

ゲームの最初には、スタート地点に駒が置かれており、このとき駒はナイトです。

あなたはこの駒を動かしてゲームを進めますが、
チェス盤のいくつかのマスは赤いマスで、
赤いマスに止まると駒がナイトから「ミニビショップ」（後述）に変わります。
同様に、駒がミニビショップのときに赤いマスに止まると駒はナイトに変わります。

すなわち、赤いマスに関するルールは以下のように記述されます。
(ここで、駒を1度動かすことを「1手」と数えることにします。)

●「k手目の移動を開始する時点で駒がナイト」かつ「k手目の移動先のマスが赤いマス」であれば、
   k+1手目から、次に赤いマスに止まるまでの間、駒はミニビショップとなる。
●「k手目の移動を開始する時点で駒がミニビショップ」かつ「k手目の移動先のマスが赤いマス」であれば、
   k+1手目から、次に赤いマスに止まるまでの間、駒はナイトとなる。

図で表すと、ナイトの利き(左)とミニビショップの利き(右)は以下のようになります。
Nがナイト、Bがミニビショップの位置を表し、
丸の書かれたマスが移動できるマスを表します。
ただし、ナイトもミニビショップもチェス盤の外に出ることはできない。

     

さて、あなたは最短何手でこのゲームをクリアすることができるでしょうか？

■■■入力■■■

H W

s1
s2
・
・
・
sH

●1行目にはチェス盤の行数H,列数W (1 <= H <= 500,1 <= W <= 500)
  がスペース区切りの整数で与えられる。
●2行目からH+1行目には、チェス盤の各マスの情報が与えられる。
  i+1行目の文字列siのj文字目がi行j列目のマスの情報を表す。
  各文字の意味は以下の通りである。
  'S' : スタート地点
  'G' : ゴール地点
  'R' : 赤いマス
  '.' : その他のマス
  これら以外の文字はsi(1 <= i <= H) には存在せず、
  'S'および'G'はちょうど1つずつ存在する。

■■■出力■■■

駒をスタート地点からゴール地点まで動かすのにかかる最短手数を、1行で出力してください。
駒がゴール地点に到達不可能な場合には-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("4 4");
            WillReturn.Add("...G");
            WillReturn.Add(".RR.");
            WillReturn.Add(".RR.");
            WillReturn.Add("S...");
            //3
            //例えば(4, 1) -> (2, 2) -> (3, 3) -> (1, 4)
            //と移動すると最短手数でクリアできます。
            //このとき、駒は ナイト -> ミニビショップ -> ナイト と変化します。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3 4");
            WillReturn.Add("...G");
            WillReturn.Add("....");
            WillReturn.Add("S...");
            //3
            //この例ではチェス盤に赤いマスはありません。
            //例えば (3, 1) -> (1, 2) -> (3, 3) -> (1, 4)
            //と移動すると最短手数でクリアできます。
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("3 3");
            WillReturn.Add(".R.");
            WillReturn.Add("RGR");
            WillReturn.Add("SR.");
            //-1
            //この例では、駒はゴール地点に到達することができません。
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static int UB_X;
    static int UB_Y;

    struct JyoutaiDef
    {
        internal int Level;
        internal int CurrX;
        internal int CurrY;
        internal bool IsKnight;
    }

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

        int[] wkArr = InputList[0].Split(' ').Select(X => int.Parse(X)).ToArray();
        int H = wkArr[0];
        int W = wkArr[1];
        char[,] BanArr = new char[W, H];
        UB_X = W - 1;
        UB_Y = H - 1;

        int StaX = -1, StaY = -1, GoalX = -1, GoalY = -1;
        for (int X = 0; X <= UB_X; X++) {
            for (int Y = 0; Y <= UB_Y; Y++) {
                BanArr[X, Y] = InputList[Y + 1][X];

                if (BanArr[X, Y] == 'S') {
                    StaX = X; StaY = Y;
                }
                if (BanArr[X, Y] == 'G') {
                    GoalX = X; GoalY = Y;
                }
            }
        }

        var Que = new Queue<JyoutaiDef>();
        JyoutaiDef WillEnqueue;
        WillEnqueue.Level = 0;
        WillEnqueue.CurrX = StaX;
        WillEnqueue.CurrY = StaY;
        WillEnqueue.IsKnight = true;
        Que.Enqueue(WillEnqueue);

        var VisitedSet = new HashSet<int>();
        VisitedSet.Add(GetHash(WillEnqueue));
        while (Que.Count > 0) {
            JyoutaiDef Dequeued = Que.Dequeue();

            //クリア判定
            if (Dequeued.CurrX == GoalX && Dequeued.CurrY == GoalY) {
                Console.WriteLine(Dequeued.Level);
                return;
            }

            Action<int, int> EnqueueSyori = (pNewX, pNewY) =>
            {
                if (pNewX < 0 || UB_X < pNewX) return;
                if (pNewY < 0 || UB_Y < pNewY) return;

                WillEnqueue.Level = Dequeued.Level + 1;
                WillEnqueue.CurrX = pNewX;
                WillEnqueue.CurrY = pNewY;
                WillEnqueue.IsKnight = Dequeued.IsKnight;
                if (BanArr[pNewX, pNewY] == 'R') {
                    WillEnqueue.IsKnight = !WillEnqueue.IsKnight;
                }

                //再訪は不可
                if (VisitedSet.Add(GetHash(WillEnqueue)) == false)
                    return;

                Que.Enqueue(WillEnqueue);
            };

            if (Dequeued.IsKnight) {
                EnqueueSyori(Dequeued.CurrX - 1, Dequeued.CurrY - 2);
                EnqueueSyori(Dequeued.CurrX + 1, Dequeued.CurrY - 2);
                EnqueueSyori(Dequeued.CurrX - 2, Dequeued.CurrY - 1);
                EnqueueSyori(Dequeued.CurrX + 2, Dequeued.CurrY - 1);
                EnqueueSyori(Dequeued.CurrX - 2, Dequeued.CurrY + 1);
                EnqueueSyori(Dequeued.CurrX + 2, Dequeued.CurrY + 1);
                EnqueueSyori(Dequeued.CurrX - 1, Dequeued.CurrY + 2);
                EnqueueSyori(Dequeued.CurrX + 1, Dequeued.CurrY + 2);
            }
            else {
                EnqueueSyori(Dequeued.CurrX - 1, Dequeued.CurrY - 1);
                EnqueueSyori(Dequeued.CurrX + 1, Dequeued.CurrY - 1);
                EnqueueSyori(Dequeued.CurrX - 1, Dequeued.CurrY + 1);
                EnqueueSyori(Dequeued.CurrX + 1, Dequeued.CurrY + 1);
            }
        }
        Console.WriteLine(-1);
    }

    //現在位置とIsKnightからハッシュ値を求める
    static int GetHash(JyoutaiDef pJyoutai)
    {
        int Hash = pJyoutai.CurrX * 10000;
        Hash += pJyoutai.CurrY * 10;
        Hash += (pJyoutai.IsKnight ? 1 : 0);
        return Hash;
    }
}

解説

ハッシュ値で再訪を防ぎつつ、幅優先探索してます。