Preparing NOJ

机器人路径规划问题

1000ms 65536K

Description:

       机器人Rob可在一个树状路径上自由移动。给定树状路径T上的起点s和终点t,机器人Rob要从s运动到t。树状路径T上有若干可移动的障碍物。由于路径狭窄,任何时刻在路径的任何位置不能同时容纳2 个物体。每一步可以将障碍物或机器人移到相邻的空顶点上。设计一个有效算法用最少移动次数使机器人从s运动到t

   对于给定的树T,以及障碍物在树T中的分布情况。计算机器人从起点s 到终点t的最少移动次数。

Input:

         输入的第1 行有3 个正整数nst,分别表示树T顶点数,起点s的编号和终点t 的编号。接下来的n 行分别对应于树T 中编号为01n-1 的顶点。每行的第1 个整数h表示顶点的初始状态,当h=1 时表示该顶点为空顶点,当h=0 时表示该顶点为满顶点,其中已有1 个障碍物。第2 个数k表示有k个顶点与该顶点相连。接下来的k个数是与该顶点相连的顶点编号。

Output:

          程序运行结束时,将计算出的机器人最少移动次数输出。如果无法将机器人从起点移动到终点,输出No solution

Sample Input:

5 0 3
1 1 2
1 1 2
1 3 0 1 3
0 2 2 4
1 1 3

Sample Output:

3

Note:

 

本题由旧版NOJ导入,来源:算法设计与实验题解

Info

NOJ

Provider NOJ

Code NOJ1355

Tags

Submitted 0

Passed 0

AC Rate 0%

Date 04/20/2019 10:03:10

Related

Nothing Yet