#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define main dummy_main
int main( ) {
return 0 ;
}
#undef main
int sz;
int arr[ 10000 ] ;
void doit( long long now, int las) {
if ( now > 2000000000 ) {
return ;
}
arr[ sz++ ] = now;
if ( las- 1 >= 0 ) {
doit( now * 10 + las - 1 , las - 1 ) ;
}
if ( las+ 1 <= 9 ) {
doit( now * 10 + las + 1 , las + 1 ) ;
}
}
class Solution{
public :
vector< int > countSteppingNumbers( int low, int high) {
int i;
vector< int > res;
if ( sz== 0 ) {
int i;
arr[ sz++ ] = 0 ;
for ( i= ( 1 ) ; i< ( 10 ) ; i++ ) {
doit( i, i) ;
}
sort( arr, arr+ sz) ;
}
for ( i= ( 0 ) ; i< ( sz) ; i++ ) {
if ( low <= arr[ i] && arr[ i] <= high) {
res.push_back ( arr[ i] ) ;
}
}
return res;
}
}
;
// cLay varsion 20191006-1
// --- original code ---
// #define main dummy_main
// {}
// #undef main
//
// int sz, arr[1d4];
//
// void doit(ll now, int las){
// if(now > 2d9) return;
// arr[sz++] = now;
// if(las-1 >= 0) doit(now * 10 + las - 1, las - 1);
// if(las+1 <= 9) doit(now * 10 + las + 1, las + 1);
// }
//
// class Solution {
// public:
// vector<int> countSteppingNumbers(int low, int high) {
// vector<int> res;
// if(sz==0){
// arr[sz++] = 0;
// rep(i,1,10) doit(i, i);
// sort(arr, arr+sz);
// }
// rep(i,sz) if(low <= arr[i] <= high) res.push_back(arr[i]);
// return res;
// }
// };
I3ByYWdtYSBHQ0Mgb3B0aW1pemUgKCJPZmFzdCIpCiNpbmNsdWRlPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgbWFpbiBkdW1teV9tYWluCmludCBtYWluKCl7CiAgcmV0dXJuIDA7Cn0KI3VuZGVmIG1haW4KaW50IHN6OwppbnQgYXJyWzEwMDAwXTsKdm9pZCBkb2l0KGxvbmcgbG9uZyBub3csIGludCBsYXMpewogIGlmKG5vdyA+IDIwMDAwMDAwMDApewogICAgcmV0dXJuOwogIH0KICBhcnJbc3orK10gPSBub3c7CiAgaWYobGFzLTEgPj0gMCl7CiAgICBkb2l0KG5vdyAqIDEwICsgbGFzIC0gMSwgbGFzIC0gMSk7CiAgfQogIGlmKGxhcysxIDw9IDkpewogICAgZG9pdChub3cgKiAxMCArIGxhcyArIDEsIGxhcyArIDEpOwogIH0KfQpjbGFzcyBTb2x1dGlvbnsKICBwdWJsaWM6CiAgdmVjdG9yPGludD4gY291bnRTdGVwcGluZ051bWJlcnMoaW50IGxvdywgaW50IGhpZ2gpewogICAgaW50IGk7CiAgICB2ZWN0b3I8aW50PiByZXM7CiAgICBpZihzej09MCl7CiAgICAgIGludCBpOwogICAgICBhcnJbc3orK10gPSAwOwogICAgICBmb3IoaT0oMSk7aTwoMTApO2krKyl7CiAgICAgICAgZG9pdChpLCBpKTsKICAgICAgfQogICAgICBzb3J0KGFyciwgYXJyK3N6KTsKICAgIH0KICAgIGZvcihpPSgwKTtpPChzeik7aSsrKXsKICAgICAgaWYobG93IDw9IGFycltpXSAgJiYgIGFycltpXSA8PSBoaWdoKXsKICAgICAgICByZXMucHVzaF9iYWNrKGFycltpXSk7CiAgICAgIH0KICAgIH0KICAgIHJldHVybiByZXM7CiAgfQp9CjsKLy8gY0xheSB2YXJzaW9uIDIwMTkxMDA2LTEKCi8vIC0tLSBvcmlnaW5hbCBjb2RlIC0tLQovLyAjZGVmaW5lIG1haW4gZHVtbXlfbWFpbgovLyB7fQovLyAjdW5kZWYgbWFpbgovLyAKLy8gaW50IHN6LCBhcnJbMWQ0XTsKLy8gCi8vIHZvaWQgZG9pdChsbCBub3csIGludCBsYXMpewovLyAgIGlmKG5vdyA+IDJkOSkgcmV0dXJuOwovLyAgIGFycltzeisrXSA9IG5vdzsKLy8gICBpZihsYXMtMSA+PSAwKSBkb2l0KG5vdyAqIDEwICsgbGFzIC0gMSwgbGFzIC0gMSk7Ci8vICAgaWYobGFzKzEgPD0gOSkgZG9pdChub3cgKiAxMCArIGxhcyArIDEsIGxhcyArIDEpOwovLyB9Ci8vIAovLyBjbGFzcyBTb2x1dGlvbiB7Ci8vIHB1YmxpYzoKLy8gICB2ZWN0b3I8aW50PiBjb3VudFN0ZXBwaW5nTnVtYmVycyhpbnQgbG93LCBpbnQgaGlnaCkgewovLyAgICAgdmVjdG9yPGludD4gcmVzOwovLyAgICAgaWYoc3o9PTApewovLyAgICAgICBhcnJbc3orK10gPSAwOwovLyAgICAgICByZXAoaSwxLDEwKSBkb2l0KGksIGkpOwovLyAgICAgICBzb3J0KGFyciwgYXJyK3N6KTsKLy8gICAgIH0KLy8gICAgIHJlcChpLHN6KSBpZihsb3cgPD0gYXJyW2ldIDw9IGhpZ2gpIHJlcy5wdXNoX2JhY2soYXJyW2ldKTsKLy8gICAgIHJldHVybiByZXM7Ci8vICAgfQovLyB9Owo=