无心人 发表于 2008-6-26 17:33:56

封锁道路问题

有一个城市,其道路有纵横各n条
组成n X n的格局,上面有n X n个点
两两相交的道路交点成为路口
有四个边界线

某天,接到上级命令,有一个疑犯要经过该城市
需要封锁道路,只能在每个道路的路口布置一个人
已知每个路口的人只能控制和它相邻的四个方向的路口和街道
   即相邻一个路口以内的道路

请问,如何布置,才能以最少的人数来封锁整个城市的道路
即找不到一个通路,使得该通路从一个边界线通向另外一个边界线,
   且线路上的路口不受布置的人的控制

[ 本帖最后由 无心人 于 2008-6-26 20:25 编辑 ]

gxqcn 发表于 2008-6-26 20:08:14

题目比较有趣。

但“只能在每个道路的十字路口布置一个人”这句有点疑问,
也就是说,n*n 个路口均为“十字路口”,就不存在“丁字”路口?:o

不过,前面有交代——有四个边界线,
不妨假设其为环形护城河,城里的格局均成“井字”形,
疑犯只要不能从城里越过护城河上的桥出去即完成任务,
这样一想,倒也合情理了。:)

无心人 发表于 2008-6-26 20:23:45

:)

呵呵,没仔细考虑哦
我还是修改下吧

gxqcn 发表于 2008-6-28 19:34:28

怎么感觉:只要派人将外围路口守住就行了?
城里面的路口完全可以不予考虑。

这样疑犯要么进不来,要么出不去,不知是否算符合要求?:o

无心人 发表于 2008-6-28 20:24:18

要求最少人数阿

mathe 发表于 2008-6-28 21:18:24

不过我对题目要求还是有点弄不明白:疑犯是从一条指定的边界出发吗?要封锁的是所有四条边界还是另外三条边界还是指定的一条边界?

无心人 发表于 2008-6-28 21:46:14

就是不能从任意边界到其他三个边界

mathe 发表于 2008-6-28 22:03:01


如果,$ceil(n/3)$个就可以了.而必要性很显然,我们仅仅考虑所有南北方向的线路,每个人最多控制3路,所以不能少于这个数

无心人 发表于 2008-6-29 10:17:27

上面的要三次旋转复制才完整吧

mathe 发表于 2008-6-29 10:54:25

哦,那你是指所有边之间都不能相同是吗?
页: [1] 2
查看完整版本: 封锁道路问题