TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P2804
  • 题目
  • P2804【CEOI 2013 DAY2】木板游戏
    限制 : 时间限制 : 5000 MS   空间限制 : 262144 KB
    评测说明 : 1s,256MB,46组,总时限5s
    问题描述

    时限:0.2s
    Mirko 和 Slavko在一个木板上玩游戏,该游戏看起来像是一棵无限大的二叉树。更详细的说,木板上有一些节点,这些节点用双向道路相连,节点分布在很多层上,顶部的根节点位于第0层,每个节点都有左右两个孩子节点,孩子节点的层号比他们的父亲节点大1。孩子与父亲间有一条道路相连。同时,位于同一层的节点,相邻两个节点间有水平的道路将它们连接起来,如下图所示:


    玩家可以沿道路移动,每步移动可以用下列方式来表达:
    字符“1”,表示从一个节点移动到它的左孩子;
    字符“2”,表示从一个节点移动到它的右孩子;
    字符“U”, 表示从一个节点移动到它的父亲节点;
    字符“L”, 表示从一个节点移动到它左边的节点;
    字符“R”, 表示从一个节点移动到它右边的节点;
    以上图为例,我们从根节点出发,经过序列"221LU"描述的路径,可以到达A节点。

    你的任务是写一个程序,计算制定的两个节点间,最少需要多少步就可以到达。
    指定的两个节点所在的位置由从根节点出发的两条路径来描述。如果给出的两条路径指向的相同的节点,输出0

    输入格式

    第一行,一个长度不超过100 000的字符序列,指向第一个节点的位置
    第二行,一个长度不超过100 000的字符序列,指向第二个节点的位置

    输出格式

    一个整数,表示最少所需的步数。

    样例输入

    样例输入1:
    111RRRRRRR
    222

    样例输入2:
    221LU
    12L2

    样例输入3:
    11111
    222222

    样例输出

    样例输出1:
    0

    样例输出2:
    3

    样例输出3:
    10