机器人路径规划问题
题目背景
**通过套取数据而直接“打表”过题者,是作弊行为,发现即棕名。**
本题**不保证**存在**可以通过满足本题数据范围的任意数据**做法。由于测试数据过水,可以通过此题的程序不一定完全正确(算法时间复杂度错误、或不保证正确性)。本题题目和数据仅供参考。本题不接受添加 hack 数据。
本题为错题。**不建议尝试或提交本题。**[关于此类题目的详细内容](https://www.luogu.com.cn/paste/isdgwj5l)
题目描述
机器人 Rob 可在一个树状路径上自由移动。给定树状路径 $T$ 上的起点 $s$ 和终点 $t$,机器人 Rob 要从 $s$ 运动到 $t$。树状路径 $T$ 上有若干可移动的障碍物。由于路径狭窄,任何时刻在路径的任何位置不能同时容纳 $2$ 个物体。每一步可以将障碍物或机器人移到相邻的空顶点上。设计一个有效算法用最少移动次数使机器人从 $s$ 运动到 $t$。对于给定的树 $T$,以及障碍物在树 $T$ 中的分布情况。计算机器人从起点 $s$ 到终点 $t$ 的最少移动次数。
输入输出格式
输入格式
第 $1$ 行有 $3$ 个正整数 $n$,$s$ 和 $t$,分别表示树 $T$ 的顶点数,起点 $s$ 的编号和终点 $t$ 的编号。
接下来的 $n$ 行分别对应于树 $T$ 中编号为 $0,1,\cdots,n-1$ 的顶点。每行的第 $1$ 个整数 $h$ 表示顶点的初始状态,当 $h=1$ 时表示该顶点为空顶点,当 $h=0$ 时表示该顶点为满顶点,其中已有 $1$ 个障碍物。第 $2$ 个数 $k$ 表示有 $k$ 个顶点与该顶点相连。接下来的 $k$ 个数是与该顶点相连的顶点编号。
输出格式
程序运行结束时,将计算出的机器人最少移动次数输出。如果无法将机器人从起点移动到终点,输出 `No solution!`。
输入输出样例
输入样例 #1
5 0 3
1 1 2
1 1 2
1 3 0 1 3
0 2 2 4
1 1 3
输出样例 #1
3
说明
题目中出现的数字均小于 $1000$。