题目描述

给定两个整数 l,r(l≤r)，请问[l,r]范围内，满足数字的任意相邻两位差值都恰好为1，且数字至少有两位的数有多少个。

样例

//输入
2
1 10
1 100
//输出
1
17

算法

(暴力枚举)

dfs，回来补坑，考试去了，祝自己好运~

C++ 代码

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

string l,r;
string temp;
set<int>ans;

int tonum(string str){
    int x=0;
    for(int i=0;i<str.length();i++){
        x=x*10+str[i]-'0';
    }
    return x;
}

void dfs(){
    //cout<<"now temp:"<<temp<<endl;
    if(temp.size()>r.size()){
        //cout<<"return because 1"<<endl;
        return;
    }
    if(tonum(temp)>tonum(r)){
        //cout<<tonum(temp)<<" "<<tonum(r)<<endl;
        //cout<<"return because 2"<<endl;
        return;
    }
    if(tonum(temp)>=tonum(l)){
        ans.insert(tonum(temp));
    }
    if(temp.size()==0){
        for(int i=0;i<=9;i++){
            //cout<<"adding "<<i<<endl;
            temp.push_back(i+'0');
            dfs();
            temp.pop_back();
            //cout<<"deleting "<<i<<endl;
        }
    }else{
        int backnum=temp.back()-'0';
        if(backnum<9){
            //cout<<"adding "<<temp.back()+1-'0'<<endl;
            temp.push_back(backnum+1+'0');
            dfs();
            temp.pop_back();
            //cout<<"deleting "<<temp.back()+1-'0'<<endl;
        }
        if(backnum>0){
            //cout<<"adding "<<temp.back()-1-'0'<<endl;
            temp.push_back(backnum-1+'0');
            dfs();
            temp.pop_back();
            //cout<<"deleting "<<temp.back()-1-'0'<<endl;
        }
    }



}

int main(){
    int t;
    cin>>t;
    while(t--){
        temp="";
        ans.clear();

        cin>>l>>r;
        if(l.length()==1)l="10";
        //cout<<l<<" "<<r<<endl;
        dfs();
        cout<<ans.size()<<endl;
    }
}