文档介绍：世界名画陈列馆问题
(不重复监视)
主讲人:张伟海
世界名画陈列馆由m×n个排列成矩形阵列的陈列室组成。为了防止名画被盗,需要在陈列室中设置警卫机器人哨位。每个警卫机器人除了监视它所在的陈列室外,还可以监视与它所在的陈列室相邻的上、下、左、右4 个陈列室。
试设计一个安排警卫机器人哨位的算法,使得名画陈列馆中每一个陈列室都在警卫机器人的监视之下,且所用的警卫机器人数最少。
★问题描述
基本思想
设陈列馆由m*n个陈列室组成,因为不存在重复监视,所以很多情况下都无解,我们采用的做法是根据
m和n的值进行分类讨论。首先,先比较m、n大小,使
m始终大于n,方面程序书写。
分三种情况讨论:
n=1 这时可以直接写出最优解:
当m mod 3=1时,将哨位置于(1,3k+1);
当m mod 3=0或2时,将哨位置于(2,3k+2),其中k=0、1、…、【m/3】。
n=2 这种情形下必须2端分别设置2个哨位,他们各监视三个陈列室。那么当m为偶数时问题就无解了。
当m为奇数时,将哨位分别至于(1,4k+3)和(2,4k+1),k=0、1、…、【m/4】。
n>2 容易验证
当n=3,m=3和n=3,m=4时无解,n=4,m=4有解。
设置哨位时,允许在的n+1行和m+1列设置哨位,但不要求的第n+1行和m+1列陈列室受到监视,那么当n>=3且m>=5时在不重复监视下有解那么n=3,m=5的不可重复监视问题一定有解。但是通过验证n=3,m=5的不可重复监视哨位设置问题无解,那么当n>=3且m>=5时在不重复监视下无解。
通过以上讨论就将所有情况分析完全了,简单写一个包含多个条件判断的程序就可以实现该算法。
哪里不懂,点哪里?
#include <i