P2775 机器人路径规划问题

    • 56通过
    • 307提交
  • 题目提供者 yyy2015c01 King of e-h
  • 评测方式 云端评测
  • 标签 网络流 网络流24题 O2优化
  • 难度 NOI/NOI+/CTSC
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目背景

    通过套取数据而直接“打表”过题者,是作弊行为,发现即棕名。

    题目描述

    机器人 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,…,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

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。