[CEOI2013] Board
题目描述
给出这样一棵“二叉树”:
- 每个节点有左右两个儿子,并如下定义每个节点的高度:假设父亲节点的高度为 $h$,那么他的两个儿子的节点的高度都是 $h+1$,相同高度的所有节点称作一层。
- 每个节点的左儿子的子树都在右儿子的子树的左边,每一层相邻的两个节点之间有一条边。 下面是一个例子:
![](https://cdn.luogu.com.cn/upload/pic/74384.png)
每一条图上的路径用一个字符串表示,字符串中的每一个字符表示一 个移动。字符仅包含如下五种:
- $\tt 1$:表示移动到当前节点的左儿子
- $\tt 2$:表示移动到当前节点的右儿子
- $\tt U$:表示移动到当前节点的父亲节点
- $\tt L$:表示移动到当前节点同层的左边的节点(保证当前节点在这一层中不是最左边的节点)
- $\tt R$:表示移动到当前节点同层的右边的节点(保证当前节点在这一层中不是最右边的节点)
用一条路径来表示这条路径的终点,例如路径:$\tt 221LU$ 就表示上图中的节点 $A$。 给出两条路径,你的任务是求出着两条路径的终点之间的最短路。
输入输出格式
输入格式
输入两行,每行一个字符串,分别表示两条路径。
输出格式
输出一行,表示两个节点之间的最短路。
输入输出样例
输入样例 #1
221LU
12L2
输出样例 #1
3
输入样例 #2
111RRRRRRR
222
输出样例 #2
0
输入样例 #3
11111
222222
输出样例 #3
10
说明
用 $D$ 表示所有经过的节点中,深度最大的节点的深度;$S$ 表示输入字符串的最大长度。
- 对于 $10\%$ 的数据,$D \leq 10$;
- 对于 $30\%$ 的数据,$D \leq 50$;
- 对于 $50\%$ 的数据,$D \leq 10^3$;
- 对于 $70\%$ 的数据,$D\leq 2 \times 10^4$;
- 对于 $100\%$ 的数据,$D \leq 10^5, S \leq 10^5$。