C#，电话数字键盘问题（Mobile Numeric Keypad problem）的算法与源代码

1 电话数字键盘问题

提供移动数字键盘。您只能按向上、向左、向右或向下至当前按钮的按钮。不允许您按最下面一行的角点按钮（即.*和#）。

移动键盘

给定一个数N，找出给定长度的可能数。

示例：

对于N=1，可能的数字数为10（0、1、2、3、…、9）

对于N=2，可能的数字数为36

可能的数字：00、08、11、12、14、22、21、23、25等等。

如果我们从0开始，有效数字将是00、08（计数：2）

如果我们从1开始，有效数字将是11、12、14（计数：3）

如果我们从2开始，有效数字将是22、21、23、25（计数：4）

如果我们从3开始，有效数字将是33、32、36（计数：3）

如果我们从4开始，有效数字将是44,41,45,47（计数：4）

如果我们从5开始，有效数字将是55,54,52,56,58（计数：5）

………………………………

………………………………

我们需要打印可能的数字。

推荐做法

移动数字键盘

试试看！

N=1是普通情况，可能的数字数为10（0，1，2，3，…，9）

对于N>1，我们需要从某个按钮开始，然后移动到四个方向（向上、向左、向右或向下）中的任何一个，该方向指向有效的按钮（不应转到*、#）。继续这样做，直到获得N个长度编号（深度优先遍历）。

递归解决方案：

移动键盘是4X3的矩形网格（4行3列）

假设Count（i，j，N）表示从位置（i，j）开始的N个长度数字的计数

如果N=1 ,计数（i，j，N）=10

其他的 Count（i，j，N）=所有Count（r，c，N-1）之和，其中（r，c）是新的

长度1从当前有效移动后的位置

位置（i，j）

下面是上述公式的三种实现代码。

2 源代码

using System;
using System.Collections;
using System.Collections.Generic;
 
namespace Legalsoft.Truffer.Algorithm
{
	public static partial class Algorithm_Gallery
	{
        #region 算法1
		private static int MNKP_Solve_Utility(char[,] keypad, int i, int j, int n)
		{
			if (keypad == null || n <= 0)
			{
				return 0;
			}
			if (n == 1)
			{
				return 1;
			}
 
			int[] row = { 0, 0, -1, 0, 1 };
			int[] col  = { 0, -1, 0, 1, 0 };
 
			int totalCount = 0;
			for (int move = 0; move < 5; move++)
			{
				int ro = i + row[move];
				int co = j + col[move];
				if (ro >= 0 && ro <= 3 && co >= 0 && co <= 2 && keypad[ro, co] != '*' && keypad[ro, co] != '#')
				{
					totalCount += MNKP_Solve_Utility(keypad, ro, co, n - 1);
				}
			}
			return totalCount;
		}
 
		public static int MNKP_Solve(char[,] keypad, int n)
		{
			if (keypad == null || n <= 0)
			{
				return 0;
			}
			if (n == 1)
			{