NOI
全国青少年信息学奥林匹克联赛(NOIPOJ)在线评测系统
NOIPOJ在线评测系统
Problem92--绘制二叉树

92: 绘制二叉树

Time Limit: 1000 Sec  Memory Limit: 128 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:]

Description

二叉树是一种基本的数据结构,它要么为空,要么由根节点,左子树和右子树组成,同时左子树和右子树也分别是二叉树。

当一颗二叉树高度为m-1时,则共有m层。除m层外,其他各层的结点数都达到最大,且叶子节点都在第m层时,这就是一个满二叉树。

现在,需要你用程序来绘制一棵二叉树,它由一颗满二叉树去掉若干结点而成。

对于一颗满二叉树,我们需要按照以下要求绘制:

1、结点用小写字母“o”表示,对于一个父亲结点,用“/”连接左子树,同样用“”连接右子树。

2、定义[i,j]为位于第i行,第j列的某个字符。若[i,j]为“/”,那么[i-1,j+1]与[i+1,j-1]要么为“o”,要么为“/”。若[i,j]为“”,那么[i-1,j-1]与[i+1,j+1]要么为“o”,要么为“”。同样,若[i,j]为第1-m层的某个节点(即“o”),那么[i+1,j-1]为“/”,[i+1,j+1]为“”。

3、对于第m层节点也就是叶子结点,若两个属于同一个父亲,那么它们之间由3个空格隔开,若两个结点相邻但不属于同一个父亲,那么它们之间由1个空格隔开。第m层左数第1个节点之前没有空格。

最后需要在一颗绘制好的满二叉树上删除n个结点(包括它的左右子树,以及与父亲的连接),原有的字符用空格替换(ASCII 32,请注意空格与ASCII 0的区别(若用记事本打开看起来是一样的,但是评测时会被算作错误答案!))。

Input

输入的第1行包含2个正整数m和n,为需要绘制的二叉树层数已经从m层满二叉树中删除的结点数。

接下来n行,每行两个正整数,表示第i层第j个结点需要被删除(1<i<=M,j<=2i-1)。


Output

输出为按照题目要求绘制的二叉树。

Sample Input Copy

2 0

Sample Output Copy

 o 
 / 
o  o

HINT

【数据范围】

30%的数据满足:n=0;

50%的数据满足:2<=m<=5;

100%的数据满足:2<=m<=10,0<=n<=10。

Source/Category

其他