c++ - ACM问题，，ACM高手快来看下啊！

PHPzhong    2017-04-17 15:34:271楼

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

> ./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;  
}

 赞 +0添加回复