Advertisement
Guest User

Untitled

a guest
Nov 18th, 2018
130
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.53 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int st, en;
  5.  
  6. int lf(int x){
  7. deque <int> d;
  8. while(x){
  9. d.push_back(x % 10);
  10. x /= 10;
  11. }
  12. reverse(d.begin(), d.end());
  13. d.push_back(d.front());
  14. d.pop_front();
  15. int ans = 0;
  16. while(!d.empty()){
  17. ans *= 10;
  18. ans += d.front();
  19. d.pop_front();
  20. }
  21. return ans;
  22. }
  23. int rg(int x){
  24. deque <int> d;
  25. while(x){
  26. d.push_back(x % 10);
  27. x /= 10;
  28. }
  29. reverse(d.begin(), d.end());
  30. d.push_front(d.back());
  31. d.pop_back();
  32. int ans = 0;
  33. while(!d.empty()){
  34. ans *= 10;
  35. ans += d.front();
  36. d.pop_front();
  37. }
  38. return ans;
  39. }
  40.  
  41. int main()
  42. {
  43.  
  44. cin >> st >> en;
  45. queue <int> q;
  46. map <int, int> used;
  47. q.push(st);
  48. used[st] = 1;
  49.  
  50. while(used[en] == 0){
  51. int i = q.front();
  52. q.pop();
  53. // cout << i << endl;
  54.  
  55. if(i / 1000 != 9 && !used[i + 1000]){
  56. used[i + 1000] = i;
  57. q.push(i + 1000);
  58. }
  59. if(i % 10 != 1 && !used[i - 1]){
  60. used[i - 1] = i;
  61. q.push(i - 1);
  62. }
  63. if(!used[lf(i)]){used[lf(i)] = i;
  64. q.push(lf(i));}
  65.  
  66. if(!used[rg(i)]){used[rg(i)] = i;
  67. q.push(rg(i));}
  68.  
  69. }
  70. vector <int> out;
  71. while(used[en] != 1){
  72. //cout << en << endl;
  73. out.push_back(en);
  74. en = used[en];
  75. }
  76. out.push_back(st);
  77. for(int i = out.size() - 1; i >= 0; i--){
  78. cout << out[i] << endl;
  79. }
  80.  
  81. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement