Q35 運命の出会いは何通り？

C#のソース

using System;
using System.Collections.Generic;

class Program
{
    const int UB = 6;

    struct JyoutaiDef
    {
        internal int X1;
        internal int Y1;
        internal int X2;
        internal int Y2;
        internal int SameLineCnt;
    }

    static void Main()
    {
        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.X1 = WillPush.Y1 = 0;
        WillPush.X2 = WillPush.Y2 = UB;
        WillPush.SameLineCnt = 0;
        stk.Push(WillPush);

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

            //クリア判定
            if (Popped.X1 == Popped.X2) Popped.SameLineCnt++;
            if (Popped.Y1 == Popped.Y2) Popped.SameLineCnt++;
            if (Popped.SameLineCnt >= 2) {
                int N1 = UB - Popped.X1 + UB - Popped.Y1;
                int R1 = UB - Popped.X1;
                int wkCombi1 = DeriveCombi(N1, R1);

                int N2 = Popped.X2 + Popped.Y2;
                int R2 = Popped.X2;
                int wkCombi2 = DeriveCombi(N2, R2);

                //積の法則で解を計上
                AnswerCnt += wkCombi1 * wkCombi2;
                continue;
            }

            Action<int, int, int, int> PushSyori = (pNewX1, pNewY1, pNewX2, pNewY2) =>
            {
                if (pNewX1 < 0 || UB < pNewX1) return;
                if (pNewY1 < 0 || UB < pNewY1) return;
                if (pNewX2 < 0 || UB < pNewX2) return;
                if (pNewY2 < 0 || UB < pNewY2) return;

                WillPush.X1 = pNewX1;
                WillPush.Y1 = pNewY1;
                WillPush.X2 = pNewX2;
                WillPush.Y2 = pNewY2;
                WillPush.SameLineCnt = Popped.SameLineCnt;
                stk.Push(WillPush);
            };
            PushSyori(Popped.X1, Popped.Y1 + 1, Popped.X2, Popped.Y2 - 1);
            PushSyori(Popped.X1, Popped.Y1 + 1, Popped.X2 - 1, Popped.Y2);
            PushSyori(Popped.X1 + 1, Popped.Y1, Popped.X2, Popped.Y2 - 1);
            PushSyori(Popped.X1 + 1, Popped.Y1, Popped.X2 - 1, Popped.Y2);
        }
        Console.WriteLine(AnswerCnt);
    }

    //nCrを求める
    static int DeriveCombi(int pN, int pR)
    {
        int WillReturn = 1;
        pR = Math.Min(pR, pN - pR);

        for (int I = pN - pR + 1; I <= pN; I++) {
            WillReturn *= I;
        }
        for (int I = 2; I <= pR; I++) {
            WillReturn /= I;
        }
        return WillReturn;
    }
}

実行結果

527552

解説

運命の出会いが発生したら、
残りの移動パターンをnCrの公式で求めて、積の法則を使ってます。