In Tất Cả Mô Hình N 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 cho một số n và phải in tất cả các mô hình N chữ số được tạo bằng cách nhấn phím bàn phím di động. Khi nhấn, chỉ được nhấn các phím gần phím hiện tại: trái, phải, lên, xuống.

Bàn phím cũ trông như sau:

Ví dụ để hiểu vấn đề:

Đầu vào: n=2 → Đầu ra: 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, ta sử dụng DFS (tìm kiếm theo chiều sâu). Trong DFS, chọn lần lượt tất cả phím làm chữ số đầu tiên. Sinh các chữ số còn lại bằng DFS (cho phép nhấn phím trái, phải, lên, xuống).

Ví Dụ

Chương trình triển khai giải pháp:

#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 << "Tất cả số " << n << " chữ số sinh từ bàn phím:\n";
    GenerateNDigitNumber(Keypad, n);
    return 0;
}

Đầu Ra

Tất cả số 2 chữ số sinh từ bàn phím là: 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