jeudi 26 novembre 2015

Unable to solve: CodeForces (TwoButtons, 520B) by using binary trees

i have been trying to solve this problem by using binary trees, because i am starting to learn about them. Please tell me if this problem can be solved by using binary trees or not, and if yes, what's wrong with my code for it that i've written so far(its in c++)?

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
using namespace std;

struct Node{
    int val;
    Node* Left;
    Node* Right;
};

Node* GetNode(int val){
    Node* newnode = new Node();
    newnode->val = val;
    newnode->Left = NULL;
    newnode->Right = NULL;
    return newnode;
}

int BFS(Node* root, int m){
    int ctr = 0;
    queue<Node*> qu;
    qu.push(root);
    while(!qu.empty()){
        Node* tmp = qu.front();
        qu.pop();
        if(tmp->val == m) return ctr;
        ctr++;
        if(tmp->Left != NULL) qu.push(tmp->Left);
        if(tmp->Right != NULL) qu.push(tmp->Right);
    }
}

int main(void){
    int n, m;
    scanf("%d%d", &n, &m);
    Node* root = GetNode(n);
    Node* tmp;
    queue<Node*> qu;
    qu.push(root);
    while(!qu.empty()){
        tmp = qu.front();
        qu.pop();
        if(tmp->val == m) continue;
        tmp->Left = GetNode(2 * tmp->val);
        qu.push(tmp->Left);
        if(tmp->val-1 >= 0){
            tmp->Right = GetNode(tmp->val - 1);
            qu.push(tmp->Right);
        }
    }
    printf("%d\n", BFS(root, m));
}

Aucun commentaire:

Enregistrer un commentaire