123好数问题：寻找第k个123好数

一个数中如果如果不含连续的'12',连续的'23',连续的'31', 就称作'123'好数.

那么, 在由123构成的n位数中, 第k个'123'好数是什么?

输入

一行, 两个正整数n,k, 用空格分隔

输出

一行, 输出由123构成的n位数中, 第k个'123'好数.

样例输入

6 14

样例输出

113322

提示

【说明提示】 1≤n≤20 k不超过满足条件的'123'好数个数

C++代码实现

#include <iostream>
#include <vector>
using namespace std;

// 判断一个数是否为'123'好数
bool isGoodNumber(int num) {
    bool has12 = false;
    bool has23 = false;
    bool has31 = false;
    int prevDigit = num % 10;
    num /= 10;
    while (num > 0) {
        int currDigit = num % 10;
        if (prevDigit == 1 && currDigit == 2) {
            has12 = true;
        } else if (prevDigit == 2 && currDigit == 3) {
            has23 = true;
        } else if (prevDigit == 3 && currDigit == 1) {
            has31 = true;
        }
        prevDigit = currDigit;
        num /= 10;
    }
    return !(has12 || has23 || has31);
}

// 生成由'123'构成的n位数
void generateGoodNumbers(int n, int currNum, int& count, int& result) {
    if (count == n) {
        result = currNum;
        return;
    }
    for (int i = 1; i <= 3; i++) {
        int nextNum = currNum * 10 + i;
        if (isGoodNumber(nextNum)) {
            count++;
            generateGoodNumbers(n, nextNum, count, result);
            if (count == n) {
                return;
            }
            count--;
        }
    }
}

int main() {
    int n, k;
    cin >> n >> k;
    
    int count = 0;
    int result = 0;
    generateGoodNumbers(n, 0, count, result);
    
    vector<int> digits;
    while (result > 0) {
        digits.push_back(result % 10);
        result /= 10;
    }
    
    for (int i = digits.size() - 1; i >= 0; i--) {
        cout << digits[i];
    }
    
    return 0;
}