kananasgarli90

Magic machine

Sep 21st, 2020
846
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. queue<int>q;
  4. int a, b;
  5. int color[10000], dis[10000];
  6. int digits(int n){
  7.     int sum = 0;
  8.     while(n > 0){
  9.         sum += n%10;
  10.         n /= 10;
  11.     }
  12.     return sum;
  13. }
  14. void bfs(){
  15.     q.push(a);
  16.     color[a] = 1;
  17.     while(!q.empty()){
  18.         int u = q.front();
  19.         int x = u*3;
  20.         int y = u - 2;
  21.         int z = u + digits(u);
  22.         if(x <= 9999 && color[x] == 0){
  23.             color[x] = 1;
  24.             q.push(x);
  25.             dis[x] = dis[u] + 1;
  26.         }
  27.         if(y > 0 && color[y] == 0){
  28.             color[y] = 1;
  29.             q.push(y);
  30.             dis[y] = dis[u] + 1;
  31.         }
  32.         if(z <= 9999 && color[z] == 0){
  33.             color[z] = 1;
  34.             q.push(z);
  35.             dis[z] = dis[u] + 1;
  36.         }
  37.         q.pop();
  38.     }
  39. }
  40. int main()
  41. {
  42.     cin>>a>>b;
  43.     bfs();
  44.     cout<<dis[b]<<endl;
  45. }
RAW Paste Data