AtCoder Beginner Contest 161 D - Lunlun Number （搜索&递推）

题意：要求第k小的相邻两位绝对值小于等于1的数。

这里介绍三种思路：

递推代码：

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1e5+5;
ll a[N]={0,1,2,3,4,5,6,7,8,9};
int main(){
	ll n,k=9,p1=1,p2=0;
	scanf("%lld",&n);
	while(k<n){
		if(abs(a[p1]%10-a[p2])<=1)
			a[++k]=a[p1]*10+a[p2];
		p2++;
		if(p2==10) p1++,p2=0;
	}
	printf("%lld\n",a[n]);
}

DFS代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+5;
ll a[N],k=0,n;
void dfs(ll i){ //不断将i作为子部分向外搜索. 
	if(i>1e10) return;
	a[++k]=i;
	for(ll j=max(ll(0),i%10-1);j<=min(ll(9),i%10+1);j++) //将i作为从最高位到十位的数,找可行的j作为个位继续dfs 
		dfs(i*10+j);  //比如 1->(10,11,12)->(|100,101,110|,|111,112|,|121,122,123|)->…… 
}
int main(){
	cin>>n;
	for(ll i=1;i<=9;i++) dfs(i);//搜索以i为最高位的lunlun数 
	sort(a+1,a+k+1);//从小到大排序 
	cout<<a[n]<<endl;
	return 0;
}

BFS代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
	ll n,ans;
	queue<ll>q;
	cin>>n;
	for(ll i=1;i<10;i++) q.push(i);
	while(n--){
		ans=q.front();
		q.pop(); 
		if(ans%10!=0) q.push(ans*10+ans%10-1); //将自己作为子部分匹配入队 
		q.push(ans*10+ans%10);
		if(ans%10!=9) q.push(ans*10+ans%10+1);
	}
	cout<<ans<<endl;
	return  0;
}