using System;

using System.Collections.Generic;

using System.Linq;

public class Program

{

    public static void Main()

    {

        Dictionary<string, int> memo = new Dictionary<string, int>();

        int result = KnightDial2(6, 2);

        int result2 = KnightDial(6, 2, memo);

        Console.WriteLine(result);

        Console.WriteLine(result2);

    }

    public static List<int> GetAdjacentNumbers(int digit)

    {

        if (digit == 0)

            return new List<int> { 4, 6 };

        if (digit == 1)

            return new List<int> { 6, 8 };

        if (digit == 2)

            return new List<int> { 7, 9 };

        if (digit == 3)

            return new List<int> { 4, 8 };

        if (digit == 4)

            return new List<int> { 3, 9, 0 };

        if (digit == 5)

            return new List<int>();

        if (digit == 6)

            return new List<int> { 1, 7, 0 };

        if (digit == 7)

            return new List<int> { 2, 6 };

        if (digit == 8)

            return new List<int> { 1, 3 };

        return new List<int> { 2, 4 };

    }

​

    public static int KnightDial(int digit, int hop, Dictionary<string, int> memo)

    {

        if (hop == 0)

            return 1;

​

        // Memo key is always one character.

        string memoKey = digit.ToString() + hop.ToString();

        if (memo.ContainsKey(memoKey))

            return memo[memoKey];

        else

        {

            // Recursion

            int sequence = 0;

            foreach (int next in GetAdjacentNumbers(digit))

            {

                sequence += KnightDial(next, hop - 1, memo);

            }

            memo[memoKey] = sequence;

            return sequence;

        }

    }

    public static int KnightDial2(int digit, int hop)

    {

        // Computes for hop 0, then 1, then 2, etc.

        int[] prior = Enumerable.Repeat(1, 10).ToArray();

        int [] current = Enumerable.Repeat(1, 10).ToArray();

        int currentHop = 1;

        while (currentHop <= hop)

        {

            current = Enumerable.Repeat(0, 10).ToArray();

            for (int i = 0; i < 10; ++i)

            {

                foreach (int adjacent in GetAdjacentNumbers(i))

                {

                    current[i] += prior[adjacent];

                }

            }

            prior = current;

            currentHop++;

        }

​

        return current[digit];

    }

​

}