打印手机键盘形成的所有 N 位数字模式

给定一个数字 N。我们需要打印由手机键盘形成的所有 N 位模式。

注意： 我们可以从手机键盘的任意按键向上、下、左、右移动，且每个模式必须包含唯一的按键。

!Mobile-keypad

示例：

输入 :   N = 3   
输出 :  所有的 3 位模式如下： 
           123, 125, 145, 147 
           236, 214, 258, 256, 254
           321, 325, 369, 365 
           412, 456, 452, 458, 478
           等等 ...

这个解决方案的思路是基于深度优先搜索（DFS）的。我们逐一选取所有键盘按键作为 N 位数字的起始位，然后，我们尝试生成由该按键形成的所有 N 位模式（使用 DFS，因为我们只能从该按键向上、左、右或下移动）。

打印模式函数 (DFS 函数) 
  将当前按键添加到模式中
  Pattern += Keypad[x][y]
 .... 将当前按键标记为已访问 
  visited[x][y] = true;
 ... 如果模式的大小等于 N 则打印模式 
 调用 DFS 处理所有 4 个相邻的键盘按键 
 __DFS_function

下面是上述思路的实现：

C++


CODEBLOCK_2fd4d4ff


Java

`

// Java program to print all n digit patterns
// formed by mobile keypad.
public class Main
{
    // A function to check if a given cell (row, col)
    // can be included in DFS
    static boolean isSafe(int x, int y, boolean[][] Visited)
    {
      
        // row number is in range, column number
        // is in range and not yet visited
        return (x >= 0 && x = 0 &&
                y < 3 && !Visited[x][y]);
    }
      
    // A utility function to do DFS for a mobile Keypad
    // matrix. It only considers the 4 neighbors as
    // adjacent vertices and print pattern of size n
    static void DFS(boolean[][] visited, int[][] Keypad, int n,
             String pattern, int x, int y)
    {
      
        // add current number to string
        pattern = pattern + Integer.toString(Keypad[x][y]);
      
        // print pattern
        if (pattern.length() == n) {
            System.out.print(pattern + " ");
            return;
        }
      
        // These arrays are used to get row and
        // column
        // numbers of 4 neighbours of a given cell
        int[] row = { 0, 1, 0, -1 };
        int[] col = { 1, 0, -1, 0 };
      
        // Mark this cell as visited
        visited[x][y] = true;
      
        // Recur for all connected neighbours
        for (int k = 0; k < 4; k++)
            if (isSafe(x + row[k], y + col[k], visited)
                && Keypad[x + row[k]][y + col[k]] != -1)
                DFS(visited, Keypad, n, pattern,
                           x + row[k], y + col[k]);
      
        // unvisited
        visited[x][y] = false;
        pattern = pattern.s