Cマガ電脳クラブ(第152回) ひと筆長旅

問題

49個の点が7×7の正方格子状に並んでいる。

Fig.1のように、Aから矢印の方向に入り、ひと筆書きで点をつないでいってBから矢印の方向に出たい。
ただし、途中直角に曲がるのは13回とし、それ以外は直進しなければならない。
同じ点を通ることは可能だが、同じパス (点と点を結ぶ線) は通れない。

点と点を結ぶ1つのパスの長さを1cmとすると、最長のルートは何cmとなるだろうか。
また、その最長のルートで、もっともたくさんの点を通るルートを1つ示してほしい。
例は、52cmのルートで46個の点を通っている。もちろん、これは最長のルートではない。

Fig.1 ひと筆書きの例

ソース

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

class Program
{
    const int UB = 7 - 1;
    const int LimitLevel = 7;

    const int HalfTansakuMaxSumLength = 6 + 4 + 6 * 5;
    const int AnswerLengthKagen = 58;

    static void Main()
    {
        var sw = System.Diagnostics.Stopwatch.StartNew();

        Console.WriteLine("正方向で半分全探索します。");
        IEnumerable<JyoutaiDef> SeiArr = ExecDFS(true);
        Console.WriteLine("メモリ使用量={0}Kバイト", GC.GetTotalMemory(false) / 1024);

        Console.WriteLine("逆方向で半分全探索します。");
        JyoutaiDef[] RevArr = ExecDFS(false).OrderByDescending(X => X.SumLength).ToArray();
        Console.WriteLine("メモリ使用量={0}Kバイト", GC.GetTotalMemory(false) / 1024);

        int AnswerLength = 0;
        int AnswerPosCnt = 0;
        foreach (JyoutaiDef EachSei in SeiArr) {
            for (int I = 0; I <= RevArr.GetUpperBound(0); I++) {
                if (EachSei.SumLength + RevArr[I].SumLength < AnswerLength) break;

                if (EachSei.CurrX != RevArr[I].CurrX) continue;
                if (EachSei.CurrY != RevArr[I].CurrY) continue;
                if (EachSei.UsedRoadSet.Overlaps(RevArr[I].UsedRoadSet))
                    continue;

                int wkLength = EachSei.SumLength + RevArr[I].SumLength;
                if (wkLength < AnswerLength) continue;
                else if (wkLength > AnswerLength) AnswerPosCnt = 0;
                AnswerLength = wkLength;

                var wkSet = new HashSet<int>(EachSei.PosSet);
                wkSet.UnionWith(RevArr[I].PosSet);
                if (wkSet.Count < AnswerPosCnt) continue;
                AnswerPosCnt = wkSet.Count;

                Console.WriteLine("解候補を発見。長さ{0}で点の数={1}", AnswerLength, AnswerPosCnt);
                var AnswerList = new List<string>(EachSei.Log);
                AnswerList.AddRange(RevArr[I].Log.AsEnumerable().Reverse().Skip(1));
                for (int J = 0; J <= AnswerList.Count - 1; J++) {
                    Console.Write(AnswerList[J]);
                    if (J == 9 || J == AnswerList.Count - 1) Console.WriteLine();
                    else Console.Write(",");
                }
            }
        }
        Console.WriteLine("経過時間={0}", sw.Elapsed);
    }

    struct JyoutaiDef
    {
        internal int Muki; //0が上向き,1が左向き,2が下向き,3が右向き
        internal int CurrX;
        internal int CurrY;
        internal int Level; //曲がった回数
        internal HashSet<int> PosSet;
        internal int SumLength;
        internal HashSet<int> UsedRoadSet;
        internal List<string> Log;
    }

    //双方向に半分全探索
    static IEnumerable<JyoutaiDef> ExecDFS(bool pIsSei)
    {
        var Stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;

        if (pIsSei) {
            WillPush.Muki = 2;
            WillPush.CurrX = 2;
            WillPush.CurrY = 0;
            WillPush.PosSet = new HashSet<int>();
            WillPush.PosSet.Add(10 * WillPush.CurrX + WillPush.CurrY);
            WillPush.Log = new List<string>();
            WillPush.Log.Add(string.Format("({0},{1})", WillPush.CurrX, WillPush.CurrY));
        }
        else {
            WillPush.Muki = 1;
            WillPush.CurrX = 6;
            WillPush.CurrY = 2;
            WillPush.PosSet = new HashSet<int>();
            WillPush.PosSet.Add(10 * WillPush.CurrX + WillPush.CurrY);
            WillPush.Log = new List<string>();
            WillPush.Log.Add(string.Format("({0},{1})", WillPush.CurrX, WillPush.CurrY));
        }
        WillPush.Level = 0;
        WillPush.SumLength = 0;
        WillPush.UsedRoadSet = new HashSet<int>();
        Stk.Push(WillPush);

        while (Stk.Count > 0) {
            JyoutaiDef Popped = Stk.Pop();

            //クリア判定
            if (Popped.Level == LimitLevel) {
                //Mukiが違うだけの葉ノードを除外
                if (Popped.Muki != 0 && Popped.Muki != 1) continue;

                //長さ合計が、解の下限未満なら、枝切り
                if (HalfTansakuMaxSumLength + Popped.SumLength < AnswerLengthKagen)
                    continue;

                yield return Popped;
                continue;
            }

            int HeniX = 0, HeniY = 0;
            if (Popped.Muki == 0) HeniY = -1; //上向き
            if (Popped.Muki == 1) HeniX = -1; //左向き
            if (Popped.Muki == 2) HeniY = 1; //下向き
            if (Popped.Muki == 3) HeniX = 1; //右向き

            WillPush.CurrX = Popped.CurrX;
            WillPush.CurrY = Popped.CurrY;

            var wkPosSet = new HashSet<int>();
            var wkUsedRoadSet = new HashSet<int>();
            while (true) {
                int PrevX = WillPush.CurrX;
                int PrevY = WillPush.CurrY;

                WillPush.CurrX += HeniX;
                WillPush.CurrY += HeniY;

                if (WillPush.CurrX < 0 || UB < WillPush.CurrX) break;
                if (WillPush.CurrY < 0 || UB < WillPush.CurrY) break;

                //使用済の道路は使用不可
                int wkUsedRoadInt = UsedRoadToInt(PrevX, PrevY, WillPush.CurrX, WillPush.CurrY);
                if (Popped.UsedRoadSet.Contains(wkUsedRoadInt)) break;

                wkUsedRoadSet.Add(wkUsedRoadInt);

                wkPosSet.Add((byte)(10 * WillPush.CurrX + WillPush.CurrY));

                WillPush.Level = Popped.Level + 1;

                WillPush.PosSet = new HashSet<int>(Popped.PosSet);
                WillPush.PosSet.UnionWith(wkPosSet);
                WillPush.SumLength = Popped.SumLength + wkPosSet.Count;

                WillPush.UsedRoadSet = new HashSet<int>(Popped.UsedRoadSet);
                WillPush.UsedRoadSet.UnionWith(wkUsedRoadSet);

                WillPush.Log = new List<string>(Popped.Log);
                WillPush.Log.Add(string.Format("({0},{1})", WillPush.CurrX, WillPush.CurrY));

                //左に曲がる場合
                WillPush.Muki = (Popped.Muki + 1) % 4;
                Stk.Push(WillPush);

                //右に曲がる場合
                WillPush.Muki = (Popped.Muki - 1 + 4) % 4;
                Stk.Push(WillPush);
            }
        }
    }

    //使用した道路をInt型で表現
    static int UsedRoadToInt(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 1000 * MinX + 100 * MinY + 10 * MaxX + MaxY;
    }
}

実行結果

省略
解候補を発見。長さ58で点の数=48
(2,0),(2,5),(5,5),(5,1),(1,1),(1,4),(6,4),(6,6),(0,6),(0,3)
(6,3),(6,0),(0,0),(0,2),(6,2)
解候補を発見。長さ58で点の数=48
(2,0),(2,4),(6,4),(6,6),(0,6),(0,3),(6,3),(6,0),(1,0),(1,5)
(5,5),(5,1),(0,1),(0,2),(6,2)
解候補を発見。長さ58で点の数=48
(2,0),(2,4),(6,4),(6,6),(0,6),(0,3),(6,3),(6,1),(1,1),(1,5)
(5,5),(5,0),(0,0),(0,2),(6,2)
解候補を発見。長さ58で点の数=48
(2,0),(2,4),(6,4),(6,6),(1,6),(1,1),(5,1),(5,5),(0,5),(0,3)
(6,3),(6,0),(0,0),(0,2),(6,2)
解候補を発見。長さ58で点の数=48
(2,0),(2,4),(6,4),(6,5),(1,5),(1,1),(5,1),(5,6),(0,6),(0,3)
(6,3),(6,0),(0,0),(0,2),(6,2)
経過時間=00:00:05.9866823

解説

双方向に半分全探索してます。