首页 > ACM题库 > HDU-杭电 > HDU 4041-Eliminate Witches!-模拟-[解题报告]HOJ
2015
04-16

HDU 4041-Eliminate Witches!-模拟-[解题报告]HOJ

Eliminate Witches!

问题描述 :

Kaname Madoka is a Magical Girl(Mahou Shoujo/Puella Magi). The duty of a Magical Girl is to eliminate Witches(Majo). Though sounds horrific, it is not a hard job for her as a powerful magical girl.

One day Madoka is eliminating Witches as usual. This time she is facing a maze full of Witches. The maze consists of rooms, each lives exactly one Witch. And there is exactly one path from one room to another. So you see, the maze can be represented as a tree, with rooms regarded as nodes on the tree.

Madoka eliminates Witches according to the following rules:
1. At first, Madoka enters the root node room of the maze.
2. If the room Madoka enters lives a Witch, Madoka will eliminate it at once, and the Witch disappear.
3. If the room has child node rooms with Witches, Madoka will choose the leftmost one and enter it.
4. Madoka won’t go back to the parent node room of a room X until Witches living in child node rooms of X are all eliminated.

See the figure below for details about a sample maze. The numbers inside nodes indicate the order of elimination of the corresponding Witches, the strings below nodes are names of Witches, and the arrow shows the tracks Madoka travels:

Astrolabe

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.

输入:

The first line contains an integer T(T<=20), indicating the number of test cases.
For each case there is only one string on a line, Madoka’s log.
It is guaranteed that the maze consists of at most 50000 rooms, and the names of Witches is a string consists of at most 10 lowercase characters, while the string of Madoka’s log consists of at most 1000000 characters, which are lowercase characters, ‘(‘, ‘)’ or ‘,’.

输出:

The first line contains an integer T(T<=20), indicating the number of test cases.
For each case there is only one string on a line, Madoka’s log.
It is guaranteed that the maze consists of at most 50000 rooms, and the names of Witches is a string consists of at most 10 lowercase characters, while the string of Madoka’s log consists of at most 1000000 characters, which are lowercase characters, ‘(‘, ‘)’ or ‘,’.

样例输入:

3 
walpurgis(charlotte(patricia,gertrud),elly,gisela) 
wuzetian 
nanoha(fate(hayate)) 

样例输出:

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 

1 
wuzetian 

3 
nanoha 
fate 
hayate 
1 2 
2 3 
3 2 
2 1

队列是用来保存遍历节点的顺序的,而栈保存的是当前遍历到的节点的父节点

模拟的过程:http://acm.hdu.edu.cn/showproblem.php?pid=4041

1):模拟过程一遍给节点名字编号;
2):当遇到 ‘(‘ 时,表示当前节点有子节点,所以把当前节点同时压入栈,和队列;
3):当遇到 ‘)’ 时,表示当前父节点的所有子节点已经遍历完,所以将当前节点压入队列,当然要再次访问父节点,所以将当前父节点也压入队列,而且,要弹出栈;当然,这时还要考虑一个问题:就是 ‘)’前面是否也为一个 ‘)’,若是,则不需要将当前节点压入队列,因为已经压入过了。但是仍然是需要将栈顶压入的,即要回到父亲的父亲;

4):当遇到 ‘,’ 时,表示遍历到了一个叶节点,将当前节点压入队列,要再次访问父节点;同上,此时还要考虑一个问题,就是’,'前面是否为一个‘)’,若是,则不需要将当前节点压入队列,同样,也是因为压入过了;

/*
Pro: 0

Sol:

date:
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <stack>
#include <cmath>
#include <queue>
#include <set>
#include <vector>
using namespace std;
char str[1000010],tmp[15];
char name[50010][12];
void solve(){
    stack <int> ss;
    queue <int> qq;
    scanf("%s",str);
    int len = strlen(str);  int j = 0, people = 0;
    for(int i = 0; i <= len;i ++){
        if(str[i] >= 'a' && str[i] <= 'z'){
            tmp[j ++] = str[i];
        }else{
            if(j != 0 || str[j] == '\0'){
                tmp[j ++] = '\0';
                strcpy(name[people ++],tmp);
                j = 0;
            }
            if(str[i] == '('){
               ss.push(people);
               qq.push(people);
            }else if(str[i] == ','){
                if(str[i - 1] != ')'){
                    qq.push(people);
                }
                qq.push(ss.top());
            }else if(str[i] == ')'){
                if(str[i - 1] != ')'){
                    qq.push(people);
                }//从这个点回到父亲节点
                qq.push(ss.top());//回到父亲节点
                ss.pop();
            }
        }
    }
    printf("%d\n",people);
    for(int i = 0; i < people; i ++)
        printf("%s\n",name[i]);
    if(qq.size() == 1) return ;
    while(!qq.empty()){
        printf("%d ",qq.front());
        qq.pop();
        printf("%d\n",qq.front());
        if(qq.size() == 1) break;
    }
}
int main(){
    int t;  scanf("%d",&t);
    for(int ca = 1; ca <= t; ca ++){
        solve();
        puts("");
    }
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/julyana_lin/article/details/7886192


  1. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。