HDU 4041 Eliminate Witches! （ACM ICPC 2011北京赛区网络赛）(二)

2014-11-23 22:08:39 ? 作者: ? 浏览: 12

wuzetian

nanoha

fate

hayate

1 2

2 3

3 2

2 1

Source

The 36th ACM/ICPC Asia Regional Beijing Site —— Online Contest

Recommend

lcy

题目大意：T组测试数据，接下来T组字符串，表示一棵树，从字符串看树的结构显而易见，然后输出这棵树访问的过程。

解题思路：模拟题，这题就是一种先序的方式，但是不是二叉树，所以自己写程序模拟一下过程就可以了

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

const int maxlen=10000010;
vector  ans;
vector  v;
map  mp;
char str[maxlen];
int len,num,pos;

void initial(){
	ans.clear();
	mp.clear();
	v.clear();
	num=1;
	pos=0;
}

void input(){
	scanf("%s",str);
	len=strlen(str);
}

void dfs(){
	if(pos>=len) return;
	string st;
	while(str[pos]>='a' && str[pos]<= 'z'){
		st.push_back(str[pos]);
		pos++;
	}
	ans.push_back(st);
	int now=num++;
	v.push_back(now);
	if(str[pos]=='('){
		pos++;
		dfs();
		v.push_back(now);
		while(str[pos]==','){
			pos++;
			dfs();
			v.push_back(now);
		}
		pos++;
	}else return;
}

void computing(){
	dfs();
}

void output(){
	printf("%d\n",num-1);
	for(int i=0;i>t;
	while(t-- >0){
		initial();
		input();
		computing();
		output();
	}
	return 0;
}

拓展：树的遍历方式（转载）

1)前序遍历

a)递归方式:

void preorder_recursive(Bitree T) /* 先序遍历二叉树的递归算法 */

{

if (T) {

visit(T); /* 访问当前结点 */

preorder_recursive(T->lchild); /* 访问左子树 */

preorder_recursive(T->rchild); /* 访问右子树 */

}

b)非递归方式

void preorder_nonrecursive(Bitree T) /* 先序遍历二叉树的非递归算法 */