【网络流24题】No.8 机器人路径规划问题
2024-10-19 09:45:45
【题意】
机器人 Rob 可在一个树状路径上自由移动。 给定树状路径 T 上的起点 s 和终点 t， 机器人 Rob 要从 s 运动到 t。 树状路径 T 上有若干可移动的障碍物。 由于路径狭窄， 任何时刻在
路径的任何位置不能同时容纳 2 个物体。每一步可以将障碍物或机器人移到相邻的空顶点上。设计一个有效算法用最少移动次数使机器人从 s 运动到 t。
输入文件示例
input.txt
5 0 3
1 1 2
1 1 2
1 3 0 1 3
0 2 2 4
1 1 3输出文件示例
output.txt
3
【分析】
写这题只是ORZ的。。。
经典难题，并未解决= =
听说网络流n^9??然而我连他跟网络流的关系都不造。。
然后网上有DP的n^6解法，好像很厉害，我就%%%好了。。
谁有兴趣就看吧。。
我就凑个整。。
2016-11-04 15:06:44
最新文章
- 媒体查询（pc端，移动端不同布局）
- 在VisualStudio2012环境下安装ArcEngine 10.0
- 用js效果做的简单焦点图
- （转）高性能JavaScript：加载和运行（动态加载JS代码）
- shell 题
- java.io.FileOutputStream类的5个构造方法
- uilable 换行标记
- 软件测试学习日志————round 0 An impressed error in my past projects
- SVD神秘值分解
- 辽宁OI2016夏令营模拟T3-chess
- sql where,group by ,having,order by用法和区别
- Ubuntu重装VMwareTools
- Android学习之基础知识十六 — Android开发高级技巧的掌握
- 开发一个微信小程序实例教程
- cmake构建时指定编译器架构(x86 or x64)
- delete 删除对象属性
- 外观模式face
- C++ 中的RTTI机制详解
- canvas技术整理
- 雷林鹏分享：C# 预处理器指令