using System;
using System.Collections.Generic;
using System.Text;

namespace EulerPath
{
    //Starting in the top left corner in a 20 by 20 grid, how many routes are there to the bottom right corner?
    class Program
    {
        static public ulong iSuccess;

        static public int iSquareSize;

        //Explore a squared 4-connected grid
        //No backtrack
        //Success if [iSquareSize,iSquareSize] is reached
        //Warning: takes 5 hours to compute on a 20x20 grid...
        private static void Explore(int fromX, int fromY, int shiftX, int shiftY/*, string path*/)
        {
            //Console.WriteLine("Explore called from " + fromX + ":" + fromY + " and going " + shiftX + "," + shiftY);
            
            int newX = fromX + shiftX;
            int newY = fromY + shiftY;
            
            //Success condition
            if ((newX == iSquareSize) && (newY == iSquareSize))
            {
                iSuccess++;
                if (iSuccess % 1000000000 == 0)
                    Console.WriteLine(DateTime.Now + " " + iSuccess / 1000000000 + " billions path found so far...");
                return;
            }

            //May I go North? Certainly not.
            //May I go West? Certainly not.

            //May I go South
            if ((newX < iSquareSize) && (shiftX != -1))
                Explore(newX, newY, 1, 0/*, path + "South:"*/);

            //May I go East
            if ((newY < iSquareSize))
                Explore(newX, newY, 0, 1/*, path + "East:"*/);
        }

        //Somehow, this problem may also be solved via the Pascal triangle
        //Only takes 2 hours to compute
        static public ulong PascalTriangle(ulong n, ulong k)
        {
            if ((n == 0) || (k == 0)) return 1;
            if (n == k) return 1;

            return PascalTriangle(n - 1, k - 1) + PascalTriangle(n - 1, k);
        }

        //Anyhow, it also can be stated as 40!/20!*20! which is damn fast to compute
        //not sure of the calculus, though.
        static public ulong fac(ulong n)
        {
            if (n == 1) return 1;
            else return n * fac(n - 1);
        }

        static void Main(string[] args)
        {
            iSuccess = 0;
            iSquareSize = 20;

            Console.WriteLine(DateTime.Now + " Start");
            
            //solution #1 5hours of computation, but it's mine
            Explore(0, 0, 0, 0/*,""*/);

            //solution #2
            //iSuccess = PascalTriangle(2 * 20, 20);

            Console.WriteLine(DateTime.Now + " Grid is " + iSquareSize + "x" + iSquareSize + " - Number of path: " + iSuccess);
            Console.ReadLine();
        }
    }
}