Q25 オシャレな靴ひもの結び方

C#のソース

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

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

        for (int I = 2; I <= 7; I++) {
            IEnumerable<int[]> PosYArrEnum = ExecDFS(I);

            Console.WriteLine("穴の数={0}での交点の最大数={1}",
                I, PosYArrEnum.Max(X => DeriveKoutenCnt(X)));
        }
        Console.WriteLine("経過時間={0}", sw.Elapsed);
    }

    struct JyoutaiDef
    {
        internal int Level;
        internal List<int> PosYList;
    }

    static IEnumerable<int[]> ExecDFS(int pAnaCnt)
    {
        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.Level = 1;
        WillPush.PosYList = new List<int>() { 0 };
        stk.Push(WillPush);

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

            //クリア判定
            if (Popped.Level == pAnaCnt * 2) {
                yield return Popped.PosYList.ToArray();
                continue;
            }

            WillPush.Level = Popped.Level + 1;

            //最後の穴は固定
            if (Popped.Level == pAnaCnt * 2 - 1) {
                WillPush.PosYList = new List<int>(Popped.PosYList) { 0 };
                stk.Push(WillPush);
                continue;
            }

            for (int I = 1; I <= pAnaCnt - 1; I++) {
                //使用済の穴は使用できない
                bool IsLeft = (Popped.Level % 2 == 0);
                bool WillContinue = false;
                for (int J = 0; J <= Popped.PosYList.Count - 1; J++) {
                    if (IsLeft && J % 2 == 1) continue;
                    if (IsLeft == false && J % 2 == 0) continue;
                    if (Popped.PosYList[J] == I) {
                        WillContinue = true;
                        break;
                    }
                }
                if (WillContinue) continue;

                WillPush.PosYList = new List<int>(Popped.PosYList) { I };
                stk.Push(WillPush);
            }
        }
    }

    struct MoveDef
    {
        internal int LeftPos;
        internal int RightPos;
    }

    //交点の数を求める
    static int DeriveKoutenCnt(int[] pPosYArr)
    {
        var MoveList = new List<MoveDef>();

        for (int I = 0; I + 1 <= pPosYArr.GetUpperBound(0); I++) {
            if (I % 2 == 0) {
                MoveList.Add(
                    new MoveDef() { LeftPos = pPosYArr[I], RightPos = pPosYArr[I + 1] });
            }
            else {
                MoveList.Add(
                    new MoveDef() { LeftPos = pPosYArr[I + 1], RightPos = pPosYArr[I] });
            }
        }

        int KoutenCnt = 0;
        for (int I = 0; I <= MoveList.Count - 1; I++) {
            for (int J = I + 1; J <= MoveList.Count - 1; J++) {
                if (MoveList[I].LeftPos > MoveList[J].LeftPos
                && MoveList[I].RightPos < MoveList[J].RightPos)
                    KoutenCnt++;
                if (MoveList[I].LeftPos < MoveList[J].LeftPos
                && MoveList[I].RightPos > MoveList[J].RightPos)
                    KoutenCnt++;
            }
        }
        return KoutenCnt;
    }
}

実行結果

穴の数=2での交点の最大数=1
穴の数=3での交点の最大数=6
穴の数=4での交点の最大数=15
穴の数=5での交点の最大数=28
穴の数=6での交点の最大数=45
穴の数=7での交点の最大数=66
経過時間=00:00:05.6278859

解説

線分の交差判定が難しかったです。