封锁道路问题
有一个城市，其道路有纵横各n条组成n X n的格局，上面有n X n个点
两两相交的道路交点成为路口
有四个边界线
某天，接到上级命令，有一个疑犯要经过该城市
需要封锁道路，只能在每个道路的路口布置一个人
已知每个路口的人只能控制和它相邻的四个方向的路口和街道
即相邻一个路口以内的道路
请问，如何布置，才能以最少的人数来封锁整个城市的道路
即找不到一个通路，使得该通路从一个边界线通向另外一个边界线，
且线路上的路口不受布置的人的控制
[ 本帖最后由 无心人 于 2008-6-26 20:25 编辑 ] 题目比较有趣。
但“只能在每个道路的十字路口布置一个人”这句有点疑问，
也就是说，n*n 个路口均为“十字路口”，就不存在“丁字”路口？:o
不过，前面有交代——有四个边界线，
不妨假设其为环形护城河，城里的格局均成“井字”形，
疑犯只要不能从城里越过护城河上的桥出去即完成任务，
这样一想，倒也合情理了。:) :)
呵呵，没仔细考虑哦
我还是修改下吧 怎么感觉：只要派人将外围路口守住就行了？
城里面的路口完全可以不予考虑。
这样疑犯要么进不来，要么出不去，不知是否算符合要求？:o 要求最少人数阿 不过我对题目要求还是有点弄不明白:疑犯是从一条指定的边界出发吗？要封锁的是所有四条边界还是另外三条边界还是指定的一条边界？ 就是不能从任意边界到其他三个边界
如果，$ceil(n/3)$个就可以了.而必要性很显然，我们仅仅考虑所有南北方向的线路，每个人最多控制3路，所以不能少于这个数 上面的要三次旋转复制才完整吧 哦，那你是指所有边之间都不能相同是吗？
页:
[1]
2