TOPIC

runtime why?

João Rafael asked 1 year ago

#include <bits/stdc++.h>

#define tam 110000

using namespace std;

typedef long long int ll;

ll z[tam], d, o, k, auxi;

void bfs(ll origem){
  queue<ll> fila;
  fila.push(origem);

  z[origem] = 0; 

  while(!fila.empty()){
    ll atual = fila.front(); 
    fila.pop();
    ll adj1 = atual+1;
    ll adj2 = atual-1;
    ll adj3 = atual*2;
    ll adj4 = atual/2;
    ll adj5 = atual*3;
    cout << "ATUAL: " << atual  << " " << d<< " " << adj1 << " " << adj2 << " " << adj3 << " " << adj4 << " " << adj5 << endl;;

    if(adj1 > 0 and adj1 < tam){
      if(z[adj1] == -1){
        fila.push(adj1);
        z[adj1] = z[atual]+1;
        if(adj1 == d) break;
      }
    }
    if(adj2 > 0 and adj2 < tam){
      if(z[adj2] == -1){
        fila.push(adj2);
        z[adj2] = z[atual]+1;
        if(adj2 == d) break;
      } 
    }

    if(adj3 < tam){
      if(z[adj3] == -1){
        fila.push(adj3);
        z[adj3] = z[atual]+1;
        if(adj3 == d) break;
      } 
    }  

    if(atual%2 == 0 and adj4 < tam and adj4 > 0){
      if(z[adj4] == -1){
        fila.push(adj4);
        z[adj4] = z[atual]+1;
        if(adj4 == d) break;
      }
    }

    if(adj5 < tam){
      if(z[adj5] == -1){
        fila.push(adj5);
        z[adj5] = z[atual]+1;
        if(adj5 == d) break;
      }  
    }

  }
}

int main(){
  ios_base::sync_with_stdio(false);

  while(cin >> o >> d >> k){

      if(o == 0 and d == 0 and k == 0)
        break;    
      memset(z, -1, sizeof(z));

      for(ll i=0;i<k;i++){
        cin >> auxi;
        z[auxi] = -2;
      }
    if(o == d)
      cout << 0 << endl;  
    else{
      if(z[o]==-2 or z[d]==-2){
        cout << -1 << endl;
        continue;
      }
      bfs(o);
      cout << z[d] << endl;  

    }
  }

  return 0;
}

This topic has not been answered yet. Be the first!

Remember not post solutions. Your post may be reviewed by our moderators.