题目描述

一个数中如果前后两位的值都不相同，并且仅由数字 1、2、3 构成，就称作“好数”。请问第 k 个“好数”是什么?

【输入格式】

输入共 1 行：
第 1 行，1 个正整数 n，k。

【输出格式】

输出共 1 行：
第 1 行，1 个正整数，由 123 构成的 n 位数中, 第 k 个"好数"。

#include <iostream>
using namespace std;

int n, k, cnt = 0,a[25];

void dfs(int step, int last)
{
	if (step > n)
	{
		cnt++;
		if (cnt == k)
		{
			for (int i = 1; i <= n; i++)
			{
				cout << a[i];
			}
		}
		return;
	}
	
	for (int i = 1; i <= 3; i++)
	{
		if (i != last)
		{
			a[step] = i;
			dfs(step + 1, i);
		}
	}
}

int main()
{
	cin >> n >> k;
	dfs(1, 0);
	return 0;
}