走迷宫

一个迷宫由R行C列格子组成，有的格子里有障碍物，不能走;有的格子是空地，可以走。 给定一个迷宫，求从左上角走到右下角最少需要走多少步(数据保证一定能走到)。只能在水平方向或垂直方向走，不能斜着走。

时间限制：1000

内存限制：65536

输入

第一行是两个整数，R和C，代表迷宫的长和宽。(1<= R，C <= 40) 接下来是R行，每行C个字符，代表整个迷宫。 空地格子用'.'表示，有障碍物的格子用'#'表示。 迷宫左上角和右下角都是'.'。

输出

输出从左上角走到右下角至少要经过多少步(即至少要经过多少个空地格子)。计算步数要包括起点和终点。

样例输入

5 5

..###

#....

#.#.#

#.#.#

#.#..

样例输出

9

表达式· 表达式树· 表达式求值

众所周知， 任何一个表达式， 都可以用一棵表达式树来表示。 例如，

表达式 a+b*c， 可以表示为如下的表达式树：

+

/ \

a *

/ \

b c

现在， 给你一个中缀表达式， 这个中缀表达式用变量来表示(不含数字)， 请你将这个中缀表达式用表达式二叉树的形式输出出来。

时间限制： 1000

内存限制： 65535

输入

输入分为三个部分。 第一部分为一行， 即中缀表达式(长度不大于 50)。

中缀表达式可能含有小写字母代表变量(a-z)， 也可能含有运算符(+、-、 *、 /、 小括号)， 不含有数字， 也不含有空格。 第二部分为一个整数 n(n < 10)， 表示中缀表达式的变量数。 第三部分有 n 行， 每行格式为 C x， C 为变量的字符， x 为该变量的值。

输出

输出分为三个部分， 第一个部分为该表达式的逆波兰式， 即该表达式树的后根遍历结果。 占一行。 第二部分为表达式树的显示， 如样例输出所示。 如果该二叉树是一棵满二叉树， 则最底部的叶子结点， 分别占据横坐标的第 1、 3、 5、 7……个位置(最左边的坐标是 1)， 然后它们的父结点的横坐标， 在两个子结点的中间。 如果不是满二叉树，则没有结点的地方， 用空格填充(但请略去所有的行末空格)。 每一行父结点与子结点中隔开一行， 用斜杠(/) 与反斜杠(\) 来表示树的关系。 /出现的横坐标位置为父结点的横坐标偏左一格， \出现的横坐标位置为父结点的横坐标偏右一格。 也就是说， 如果树高为 m， 则输出就有 2m-1 行。 第三部分为一个整数， 表示将值代入变量之后，该中缀表达式的值。 需要注意的一点是， 除法代表整除运算， 即舍弃小数点后的部分。 同时， 测试数据保证不会出现除以 0 的现象。

样例输入

a+b*c

3

a 2

b 7

c 5

样例输出

abc*+

+

/ \

a *

/ \

b c

37

快速堆猪

小明有很多猪，他喜欢玩叠猪游戏，就是将猪一头头叠起来。猪叠上去后，还可以把顶上的猪拿下来。小明知道每头猪的重量，而且他还随时想知道叠在那里的猪最轻的是多少斤。

时间限制：1000

内存限制：65536

输入

有三种输入1)push n n是整数(0<=0 <=20000)，表示叠上一头重量是n斤的新猪 2)pop 表示将猪堆顶的猪赶走。如果猪堆没猪，就啥也不干 3)min 表示问现在猪堆里最轻的猪多重。如果猪堆没猪，就啥也不干 输入总数不超过100000条

输出

对每个min输入，输出答案。如果猪堆没猪，就啥也不干

样例输入

pop

min

push 5

push 2

push 3

min

push 4

min

样例输出

2

2

重建二叉树

给定一棵二叉树的前序遍历和中序遍历的结果，求其后序遍历。

时间限制：1000

内存限制：65536

输入

输入可能有多组，以EOF结束。 每组输入包含两个字符串，分别为树的前序遍历和中序遍历。每个字符串中只包含大写字母且互不重复。

输出

对于每组输入，用一行来输出它后序遍历结果。

样例输入

DBACEGF ABCDEFG

BCAD CBAD

样例输出

ACBFGED

CDAB

样例输入

DBACEGF ABCDEFG

BCAD CBAD

样例输出

ACBFGED

CDAB