封锁道路问题

无心人 · 发表于 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 个路口均为“十字路口”，就不存在“丁字”路口？

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

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

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

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

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

这样疑犯要么进不来，要么出不去，不知是否算符合要求？

无心人 · 发表于 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

哦，那你是指所有边之间都不能相同是吗？

账号		自动登录	找回密码
密码			欢迎注册

[讨论] 封锁道路问题

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。