发信人: alexatnt(千), 信区: Algorithm
标 题: N个机器人同时走迷宫
发信站: 饮水思源 (2014年07月26日06:45:06 星期六)

问道题,一个简单的走二维格子迷宫求最短路径的问题,现在加上了个条件,就是迷宫里
有N个机器人,每个机器人起点不一样,但终点都相同。要求走的过程中不能碰撞。单位时
间内,每个机器人可以上下左右走一格,也可以原地等待。求怎么安排花费时间最短。感
觉像是DP,但又想不出怎么个DP法。
--

http://bbs.sjtu.edu.cn/file/test/1142648408115481.JPG
http://bbs.sjtu.edu.cn/file/test/1142648450145130.JPG

※ 来源:·饮水思源 bbs.sjtu.edu.cn·[FROM: 69.114.100.31]