封锁道路问题

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

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

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

[讨论] 封锁道路问题

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