In tất cả n mẫu chữ số được tạo bởi Bàn phím di động trong C ++

Trong bài toán này, chúng ta được cung cấp một số n và chúng ta phải in tất cả các mẫu chữ số N được tạo thành bằng cách nhấn nút trên bàn phím di động. Trong khi nhấn các nút, chúng ta chỉ có thể nhấn các nút lân cận của nút hiện tại, tức là chỉ có thể nhấn các phím trái, phải, lên, xuống.

Hãy xem bàn phím cũ trông như thế nào -

Hãy lấy một ví dụ để hiểu vấn đề

Input: n=2
Output: 12 14 21 23 25 32 36 41 45 47 52 54 56 58 63 65 69 74 78 85 87 89 80 96 98

Để giải quyết vấn đề này, chúng tôi sẽ sử dụng tìm kiếm theo chiều sâu (DFS). trong DFS, chúng tôi sẽ chọn từng phím một trên bàn phím làm chữ số đầu tiên của số. Bây giờ, chúng tôi sẽ tạo các chữ số còn lại của số bằng cách sử dụng DFS (cho phép trái, phải, lên hoặc xuống key stokes).

Ví dụ

Chương trình thực hiện giải pháp trên -

#include <bits/stdc++.h>
using namespace std;
bool isSafe(int x, int y, bool Visited[][3]) {
   return (x >= 0 && x < 4 && y >= 0 && y < 3 && !Visited[x][y]);
}
void searchNumber(bool visited[][3], int Keypad[][3], int n, string pattern, int x, int y) {
   pattern.push_back((Keypad[x][y] + '0'));
   if (pattern.size() == n) {
      cout<<pattern<<"\t";
      return;
   }
   static int row[] = { 0, 1, 0, -1 };
   static int col[] = { 1, 0, -1, 0 };
   visited[x][y] = true;
   for (int k = 0; k < 4; k++)
      if (isSafe(x + row[k], y + col[k], visited) && Keypad[x + row[k]][y + col[k]] != -1)
   searchNumber(visited, Keypad, n, pattern, x + row[k], y + col[k]);
   visited[x][y] = false;
   pattern.pop_back();
}
void GenerateNDigitNumber(int Keypad[][3], int n) {
   bool visited[4][3];
   memset(visited, false, sizeof(visited));
   for (int i = 0; i < 4; i++)
      for (int j = 0; j < 3; j++)
         if (Keypad[i][j] != -1)
            searchNumber(visited, Keypad, n, "", i, j);
}
int main() {
   int Keypad[4][3] ={
      { 1, 2, 3 },
      { 4, 5, 6 },
      { 7, 8, 9 },
      { -1, 0, -1 }
   };
   int n = 2;
   cout<<"All "<<n<<" digit number generated from keypad are :\n";
   GenerateNDigitNumber(Keypad, n);
   return 0;
}

Đầu ra

All 2 digit number generated from keypad are −
12 14 23 25 21 36 32 45 47 41 56 58 54 52 69 65 63 78 74 89 80 87 85 98 96 08