พิมพ์ Jumping Numbers น้อยกว่าหรือเท่ากับค่าที่กำหนดใน C++

ภาพรวมปัญหา

ได้รับตัวเลข n ต้องพิมพ์ Jumping Numbers ทั้งหมด ≤ n

Jumping Numbers คืออะไร?

ตัวเลขที่หลักติดกันต่างกัน 1 เท่านั้น เช่น 4565, 98, 7

ตัวเลข 1 หลักทั้งหมดเป็น Jumping Numbers

235 ไม่ใช่ เพราะ 3 และ 5 ต่างกัน 2

ตัวอย่าง

Input: N = 32
Output: 0 1 2 3 4 5 6 7 8 9 10 12 21 23 32

วิธีแก้ปัญหา (BFS บน Graph)

สมมติกราฟที่ 0 เป็นโหนดเริ่มต้น สร้างโหนดถัดไปโดยเพิ่มหลักสุดท้าย ±1 (ยกเว้น 0 และ 9) ใช้ BFS/DFS ไปเยี่ยมโหนดที่ ≤ N

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

void traverse(int N, int num) {
    queue<int> q;
    q.push(num);
    while (!q.empty()) {
        num = q.front(); q.pop();
        if (num <= N) {
            cout << num << " ";
            int last_dig = num % 10;
            if (last_dig == 0)
                q.push((num * 10) + (last_dig + 1));
            else if (last_dig == 9)
                q.push((num * 10) + (last_dig - 1));
            else {
                q.push((num * 10) + (last_dig - 1));
                q.push((num * 10) + (last_dig + 1));
            }
        }
    }
}

void printJumpingNumber(int N) {
    cout << 0 << " ";
    for (int i = 1; i <= 9 && i <= N; i++)
        traverse(N, i);
}

int main() {
    int N = 54;
    cout << "Jumping Numbers less than " << N << " are:\n";
    printJumpingNumber(N);
    return 0;
}

ผลลัพธ์ (Output)

Jumping Numbers less than 54 are:
0 1 10 12 2 21 23 3 32 34 4 43 45 5 54 6 7 8 9