daily pastebin goal
57%
SHARE
TWEET

Untitled

a guest Aug 12th, 2017 48 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <queue>
  3.  
  4. using namespace std;
  5.  
  6. queue<int> q;
  7. int dist[100001];
  8. bool check[100001];
  9. int A, B, N, M;
  10.  
  11. bool isInB(int n) {
  12.     if(n >= 0 && n <= 100000)
  13.         return true;
  14.     else
  15.         return false;
  16. }
  17.  
  18. void pushNext(int now) {
  19.     int nextDist = dist[now] + 1;
  20.     if(isInB(now+1))
  21.         if(!check[now+1]) {
  22.             q.push(now+1);
  23.             dist[now+1] = nextDist;
  24.             check[now+1] = true;
  25.         }
  26.  
  27.     if(isInB(now-1))
  28.         if(!check[now-1]) {
  29.             q.push(now-1);
  30.             dist[now-1] = nextDist;
  31.             check[now-1] = true;
  32.         }
  33.  
  34.     if(isInB(now+A))
  35.         if(!check[now+A]) {
  36.             q.push(now+A);
  37.             dist[now+A] = nextDist;
  38.             check[now+A] = true;
  39.         }
  40.  
  41.     if(isInB(now-A))
  42.         if(!check[now-A]) {
  43.             q.push(now-A);
  44.             dist[now-A] = nextDist;
  45.             check[now-A] = true;
  46.         }
  47.  
  48.     if(isInB(now+B))
  49.         if(!check[now+B]) {
  50.             q.push(now+B);
  51.             dist[now+B] = nextDist;
  52.             check[now+B] = true;
  53.         }
  54.  
  55.     if(isInB(now-B))
  56.         if(!check[now-B]) {
  57.             q.push(now-B);
  58.             dist[now-B] = nextDist;
  59.             check[now-B] = true;
  60.         }
  61.  
  62.     if(isInB(now*A))
  63.         if(!check[now*A]) {
  64.             q.push(now*A);
  65.             dist[now*A] = nextDist;
  66.             check[now*A] = true;
  67.         }
  68.  
  69.     if(isInB(now*B))
  70.         if(!check[now*B]) {
  71.             q.push(now*B);
  72.             dist[now*B] = nextDist;
  73.             check[now*B] = true;
  74.         }
  75. }
  76.  
  77. int main()
  78. {
  79.     cin >> A >> B >> N >> M;
  80.  
  81.     check[N] = true;
  82.     dist[N] = 0;
  83.  
  84.     q.push(N);
  85.     while(!q.empty()) {
  86.         int now = q.front(); q.pop();
  87.         if(now == M)
  88.            break;
  89.  
  90.         pushNext(now);
  91.     }
  92.  
  93.     cout << dist[M] << endl;
  94. }
RAW Paste Data
Top