Problem:Given a positive number x, print all Jumping Numbers smaller than or equal to x. A number is called as a Jumping Number if all adjacent digits in it differ by 1. The difference between ‘9’ and ‘0’ is not considered as 1. All single digit numbers are considered as Jumping Numbers. For example 7, 8987 and 4343456 are Jumping numbers but 796 and 89098 are not.
Solution Hint: use BFS to find the next digit, constraint: new digit +/- 1 from the previous digit.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 |
#include <stdio.h> #include <queue> using namespace std; int main() { //code int t,n,val,v,v1,tmp; queue<int> cue; scanf("%d",&t); while(t--) { scanf("%d",&n); if(n==0) { printf("0\n"); continue; } printf("0"); for(int i=1;i<10;i++) { if(i<=n) { while(!cue.empty()) cue.pop(); cue.push(i);//[idx++]=i; while(!cue.empty()) { val = cue.front(); printf(" %d",val); cue.pop(); tmp= val%10; if(tmp-1>=0) { v=val*10+(tmp-1); if(v<=n) cue.push(v); } if(tmp+1<10) { v1=val*10+(tmp+1); if(v1<=n && v1!=v) cue.push(v1); } } } } printf("\n"); } return 0; } |