无法解决：CodeForces (TwoButtons, 520B) 通过使用二叉树

Question

我一直在尝试使用二叉树来解决这个问题，因为我开始了解它们。请告诉我这个问题是否可以通过使用二叉树来解决，如果是的话，我到目前为止编写的代码有什么问题（它是用 C++ 编写的）？它给出了错误的答案...

问题： 瓦夏发现了一个奇怪的装置。在设备的前面板上有：一个红色按钮、一个蓝色按钮和一个显示正整数的显示屏。单击红色按钮后，设备会将显示的数字乘以二。单击蓝色按钮后，设备会从显示屏上的数字中减一。如果在某个时候该数字不再为正数，则该设备会发生故障。显示器可以显示任意大的数字。最初，显示屏显示数字 n.

Bob 想在显示器上显示数字 m。为了达到这个结果，他至少需要点击多少次？

输入输入的第一行也是唯一一行包含两个不同的整数 n 和 m (1 ≤ n,⟩m ≤ 104)，由 space .

分隔

输出打印一个数字 — 从数字 n 中取出数字 m 所需的按下按钮的最少次数。

#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) break;
        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));
}

Answer 1

main() 中的 while 循环是无限循环。没有条件可以终止该循环。您的程序不断为队列分配内存，直到用完 space.

您的 continue 应该是 break。不过，这个 while() 循环的效率非常低，因为它生成的队列呈指数增长。

Answer 2

您需要存储节点的级别（根级别：0），因为这将为您提供获取 m 所需的步骤。

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

那么getNode就会多一个参数(level):

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

树的根从第 0 级开始：

Node* root = GetNode(n,0);

当你想获得一个新节点时，级别将是父节点的级别+1：

node->Left = GetNode(value,(node->lev)+1);

你的中断不是在最有效的地方，你应该在添加一个新节点（值为 tmp->val*2 或 tmp->val-1）时停止你的循环，并且其中任何一个都是 m (并且不要忘记更新 tmp，您将使用它来打印答案）。

另一个让你的算法高效的重要事情是知道你的节点应该什么时候添加到树中。其中之一是“如果它们是如果 tmp->val-1 小于或等于 0（数字必须始终为正数）。此外，如果节点高于 m，则不应增加，因此 tmp->left仅当 tmp->val < m.

时才会创建

最后，如果你到达了一个已经在你的树中的数字，那么你应该添加那个节点（这个验证是用 !nit.count(x) 完成的，这意味着 "if I dont have any x in my map"）。

//this if comes inmediatly after reading n and m
if (n==m){
    cout<<0<<endl;
    return 0;
}
while(!qu.empty()){
    tmp = qu.front();
    qu.pop();
    if (!nit.count(2 * tmp->val) && (tmp->val<m)){
        tmp->Left = GetNode(2 * tmp->val,tmp->lev+1);
        //cout<<2 * tmp->val<<endl;
        if ((2 * tmp->val)==m){
            tmp=tmp->Left; break;
        }
        nit[2 * tmp->val]++;
        qu.push(tmp->Left);
    }
    if(!nit.count(tmp->val-1) && (tmp->val-1 > 0)){
        tmp->Right = GetNode(tmp->val - 1,tmp->lev+1);
        //cout<<tmp->val-1<<endl;
        if ((tmp->val-1)==m){
            tmp=tmp->Right; break;
        }
        nit[tmp->val-1]++;
        qu.push(tmp->Right);
    }
}

现在你有了答案：

printf("%d\n",tmp->lev);

这是完整的代码：

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

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

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


int main(void){
    int n, m;
    map<int,int>nit;
    scanf("%d%d", &n, &m);
    if (n==m){
        cout<<0<<endl;
        return 0;
    }
    Node* root = GetNode(n,0);
    nit[n++];
    Node* tmp;
    queue<Node*> qu;
    qu.push(root);

    while(!qu.empty()){
        tmp = qu.front();
        qu.pop();
        if (!nit.count(2 * tmp->val) && (tmp->val<m)){
            tmp->Left = GetNode(2 * tmp->val,tmp->lev+1);
            //cout<<2 * tmp->val<<endl;
            if ((2 * tmp->val)==m){
                tmp=tmp->Left; break;
            }
            nit[2 * tmp->val]++;
            qu.push(tmp->Left);
        }
        if(!nit.count(tmp->val-1) && (tmp->val-1 > 0)){
            tmp->Right = GetNode(tmp->val - 1,tmp->lev+1);
            //cout<<tmp->val-1<<endl;
            if ((tmp->val-1)==m){
                tmp=tmp->Right; break;
            }
            nit[tmp->val-1]++;
            qu.push(tmp->Right);
        }
    }
    printf("%d\n",tmp->lev);
}

对不起我的英文c:

无法解决：CodeForces (TwoButtons, 520B) 通过使用二叉树

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

c++

binary-tree

c++11