Q31 最短経路の計算

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static int UB_X;
    static int UB_Y;

    static void Main()
    {
        Console.WriteLine("2*2では、{0}通り", Solve(2, 2));
        Console.WriteLine("6*6では、{0}通り", Solve(6, 6));
    }

    struct JyoutaiDef
    {
        internal int Level;
        internal int CurrX1;
        internal int CurrY1;
        internal int CurrX2;
        internal int CurrY2;
        internal HashSet<string> UsedRoadSet;
        internal string Log1;
        internal string Log2;
    }

    //双方向探索で解く
    static int Solve(int pX, int pY)
    {
        UB_X = pX; UB_Y = pY;

        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        //対象解の除外で最初の方向は固定する
        WillPush.Level = 2;
        WillPush.CurrX1 = 0; WillPush.CurrY1 = 1;
        WillPush.CurrX2 = 1; WillPush.CurrY2 = 0;
        WillPush.UsedRoadSet = new HashSet<string>();
        WillPush.UsedRoadSet.Add(UseRoadToStr(0, 0, 0, 1));
        WillPush.UsedRoadSet.Add(UseRoadToStr(0, 0, 1, 0));
        WillPush.Log1 = string.Format("({0},{1})", 0, 1);
        WillPush.Log2 = string.Format("({0},{1})", 1, 0);
        stk.Push(WillPush);

        int AnswerCnt = 0;
        while (stk.Count > 0) {
            JyoutaiDef Popped = stk.Pop();

            //クリア判定
            bool IsClear1 = (Popped.CurrX1 == UB_X && Popped.CurrY1 == UB_Y);
            bool IsClear2 = (Popped.CurrX2 == UB_X && Popped.CurrY2 == UB_Y);

            if (IsClear1 && IsClear2) {
                AnswerCnt++;
                //Console.WriteLine("解{0}を発見", AnswerCnt);
                //Console.WriteLine("経路1={0}", Popped.Log1);
                //Console.WriteLine("経路2={0}", Popped.Log2);
                continue;
            }

            bool IsOuro; //往路ならTrue、復路ならFalse
            if (IsClear1 == false && IsClear2 == false) {
                IsOuro = (Popped.Level % 2 == 0);
            }
            else if (IsClear1 == false) IsOuro = true;
            else IsOuro = false;

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

                WillPush.Level = Popped.Level + 1;
                if (IsOuro) { //往路の場合
                    WillPush.CurrX1 = pNewX;
                    WillPush.CurrY1 = pNewY;
                    WillPush.CurrX2 = Popped.CurrX2;
                    WillPush.CurrY2 = Popped.CurrY2;

                    //使用済の道路は使用不可
                    string UseRoadStr = UseRoadToStr(Popped.CurrX1, Popped.CurrY1,
                                                     pNewX, pNewY);
                    if (Popped.UsedRoadSet.Contains(UseRoadStr)) return;
                    WillPush.UsedRoadSet = new HashSet<string>(Popped.UsedRoadSet);
                    WillPush.UsedRoadSet.Add(UseRoadStr);
                    WillPush.Log1 = Popped.Log1 + ","
                        + string.Format("({0},{1})", pNewX, pNewY);
                    WillPush.Log2 = Popped.Log2;
                    stk.Push(WillPush);
                }
                else { //復路の場合
                    WillPush.CurrX1 = Popped.CurrX1;
                    WillPush.CurrY1 = Popped.CurrY1;
                    WillPush.CurrX2 = pNewX;
                    WillPush.CurrY2 = pNewY;

                    //使用済の道路は使用不可
                    string UseRoadStr = UseRoadToStr(Popped.CurrX2, Popped.CurrY2,
                                                     pNewX, pNewY);
                    if (Popped.UsedRoadSet.Contains(UseRoadStr)) return;
                    WillPush.UsedRoadSet = new HashSet<string>(Popped.UsedRoadSet);
                    WillPush.UsedRoadSet.Add(UseRoadStr);
                    WillPush.Log1 = Popped.Log1;
                    WillPush.Log2 = Popped.Log2 + ","
                        + string.Format("({0},{1})", pNewX, pNewY);
                    stk.Push(WillPush);
                }
            };

            //往路の場合
            if (IsOuro) {
                PushSyori(Popped.CurrX1, Popped.CurrY1 + 1);
                PushSyori(Popped.CurrX1 + 1, Popped.CurrY1);
            }
            else { //復路の場合
                PushSyori(Popped.CurrX2, Popped.CurrY2 + 1);
                PushSyori(Popped.CurrX2 + 1, Popped.CurrY2);
            }
        }
        return AnswerCnt * 2;
    }

    //使用した道路をString型で表現
    static string UseRoadToStr(int pFromX, int pFromY, int pToX, int pToY)
    {
        int MinX = Math.Min(pFromX, pToX);
        int MaxX = Math.Max(pFromX, pToX);

        int MinY = Math.Min(pFromY, pToY);
        int MaxY = Math.Max(pFromY, pToY);

        return string.Format("({0},{1})-({2},{3})", MinX, MinY, MaxX, MaxY);
    }
}

実行結果

2*2では、10通り
6*6では、100360通り

解説

双方向探索で解いてます。