Rumah  >  Soal Jawab  >  teks badan

c++ - ACM问题,,ACM高手快来看下啊!

天蓬老师天蓬老师2764 hari yang lalu532

membalas semua(1)saya akan balas

  • PHPz

    PHPz2017-04-17 15:34:27

    这个其实不难,我修改了下代码,写了点注释,你可以看看。
    加了点输出语句,显示下搜索计算的过程

    > ./a.out               
    dudduduudu
    0 --d-> 1 [T(0),BT(0),son_nu(1)]
    0 <-u-- 1 
    0 --d-> 2 [T(1),BT(1),son_nu(2)]
            2 --d-> 3 [T(1),BT(2),son_nu(1)]
            2 <-u-- 3 
            2 --d-> 4 [T(2),BT(3),son_nu(2)]
            2 <-u-- 4 
    0 <-u-- 2 
    0 --d-> 5 [T(2),BT(4),son_nu(3)]
    0 <-u-- 5 
    2 => 4

    修改的代码如下

    #include <cstdio>  
    #include <algorithm>  
    #include <cmath>
    #include <vector>
    using namespace std;  
      
    const int N = 100100;  
    char s[N];  
    int curTreeDep, curBtreeDep;    // 当前一般树和二叉树的深度
    
    // ======>>> 添加输出部分,可删除
    int nodeID = 0;
    std::vector<int> searchStack;
    int tabscount = 0;
    // <<<===== 添加输出部分结束
    
    
    void dfs(int &i, int treeDep, int btreeDep)  
    {
        // 以传入的深度与当前深度中的较大者为当前深度
        curTreeDep = max(curTreeDep, treeDep);  
        curBtreeDep = max(curBtreeDep, btreeDep);  
    
        // 第几个子(当前搜索到的节点是)
        int son_nu = 1;
        while(s[i])  
        {  
            // d 为往下搜索,说明访问的是一个子节点
            if(s[i] == 'd'){
    
                // ======>>> 添加输出部分,可删除
                for(int i = 0; i< tabscount;++i){
                    printf("        ");
                }
                ++tabscount;
    
                printf("%d --d-> %d [T(%d),BT(%d),son_nu(%d)]\n",
                            searchStack.back(),++nodeID,
                            curTreeDep,curBtreeDep,son_nu);
                searchStack.push_back(nodeID);
                // <<<===== 添加输出部分结束
    
                // 递归下去继续访问
                dfs(++i, treeDep + 1, btreeDep + son_nu);
                // 当上面调用完成,说明是遇到了 u 
                // 也就是向上访问父节点
                // 所以这里son_nu要加1,表示再次遇到d的时候
                // 这个访问节点是第几个孩子
                ++son_nu;
            }
            else{
                // ======>>> 添加输出部分,可删除
                --tabscount;
                for(int i = 0; i< tabscount;++i){
                    printf("        ");
                }
                int sid = searchStack.back();
                searchStack.pop_back();
                printf("%d <-u-- %d \n",searchStack.back(),sid);
                // <<<===== 添加输出部分结束
    
                ++i;    // i自增,下一个
                return;    // 递归结束控制
            }  
        }  
    }  
    int main()  
    {  
        if(scanf("%s", s) < 1){
            printf("%d => %d\n", 0,0);  
            return 0;
        }
    
        int i = 0;  
        curTreeDep = curBtreeDep = -1;
        searchStack.push_back(nodeID);
        dfs(i, 0, 0);  
        printf("%d => %d\n", curTreeDep, curBtreeDep);  
        return 0;  
    }

    balas
    0
  • Batalbalas