HDU 4041 Eliminate Witches! （ACM ICPC 2011北京赛区网络赛）
HDU 4041 Eliminate Witches! （ACM ICPC 2011 北京赛区网络赛题目）
Eliminate Witches!
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 863 Accepted Submission(s): 342
After finishes her task, Madoka just make a brief log like this:
"walpurgis(charlotte(patricia,gertrud),elly,gisela)"
which represents the tree-like maze identifying rooms by the names of Witches living in them.
Akemi Homura, a classmate of Madoka, also a Magical Girl, is a mad fan of her. She wants to take detailed notes of everything Madoka do! Apparently the log Madoka made is hard to read, so Homura decide to make a new one of her own.
The new log should contain the following information:
1. The number of rooms of the maze
2. Names of Witches in all rooms.
3. The tracks Madoka travels. (represented by the number identifying the node)
So the new log should be like this:
6
walpurgis
charlotte
patricia
gertrud
elly
gisela
1 2
2 3
3 2
2 4
4 2
2 1
1 5
5 1
1 6
6 1
However, the maze may be very large, so Homura nees a program to help her.
InputOutputSample InputSample OutputSourceRecommend#include <iostream>#include <cstring>#include <cstdio>#include <string>#include <map>#include <cstring>#include <vector>using namespace std;const int maxlen=10000010;vector <string> ans;vector <int> v;map <string,int> 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<ans.size();i++){printf("%s\n",ans[i].c_str());} for(int i=0;i<v.size()-1;i++){printf("%d %d\n",v[i],v[i+1]);}printf("\n");}int main(){int t;cin>>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) /* 先序遍历二叉树的非递归算法 */
{
initstack(S);
push(S,T); /* 根指针进栈 */
while(!stackempty(S)) {
while(gettop(S,p)&&p) { /* 向左走到尽头 */
visit(p); /* 每向前走一步都访问当前结点 */
push(S,p->lchild);
}
pop(S,p);
if(!stackempty(S)) { /* 向右走一步 */
pop(S,p);
push(S,p->rchild);
}
}
}
2)中序遍历
a)递归方式
void inorder_recursive(Bitree T) /* 中序遍历二叉树的递归算法 */
{
if (T) {
inorder_recursive(T->lchild); /* 访问左子树 */
visit(T); /* 访问当前结点 */
inorder_recursive(T->rchild); /* 访问右子树 */
}
}
b)非递归方式
void inorder_nonrecursive(Bitree T)
{
initstack(S); /* 初始化栈 */
push(S, T); /* 根指针入栈 */
while (!stackempty(S)) {
while (gettop(S, p) && p) /* 向左走到尽头 */
push(S, p->lchild);
pop(S, p); /* 空指针退栈 */
if (!stackempty(S)) {
pop(S, p);
visit(p); /* 访问当前结点 */
push(S, p->rchild); /* 向右走一步 */
}
}
}
3)后序遍历
a)递归方式
void postorder_recursive(Bitree T) /* 中序遍历二叉树的递归算法 */
{
if (T) {
postorder_recursive(T->lchild); /* 访问左子树 */
postorder_recursive(T->rchild); /* 访问右子树 */
visit(T); /* 访问当前结点 */
}
}
b)非递归方式
typedef struct {
BTNode* ptr;
enum {0,1,2} mark;
} PMType; /* 有mark域的结点指针类型 */
void postorder_nonrecursive(BiTree T) /*
后续遍历二叉树的非递归算法 */
{
PMType a;
initstack(S); /* S的元素为PMType类型 */
push (S,{T,0}); /* 根结点入栈 */
while(!stackempty(S)) {
pop(S,a);
switch(a.mark)
{
case 0:
push(S,{a.ptr,1}); /* 修改mark域 */
if(a.ptr->lchild)
push(S,{a.ptr->lchild,0}); /* 访问左子树 */
break;
case 1:
push(S,{a.ptr,2}); /* 修改mark域 */
if(a.ptr->rchild)
push(S,{a.ptr->rchild,0}); /* 访问右子树 */
break;
case 2:
visit(a.ptr); /* 访问结点 */
}
}
}