《世界名画陈列馆问题课件》由会员分享，可在线阅读，更多相关《世界名画陈列馆问题课件（11页珍藏版）》请在金锄头文库上搜索。
1、世界名画陈列馆问题世界名画陈列馆问题(不重复监视不重复监视)主讲人：张伟海主讲人：张伟海 世界名画陈列馆由世界名画陈列馆由mn个排列成矩形阵列的个排列成矩形阵列的陈列室组成。为了防止名画被盗，需要在陈列室陈列室组成。为了防止名画被盗，需要在陈列室中设置警卫机器人哨位。每个警卫机器人除了监中设置警卫机器人哨位。每个警卫机器人除了监视它所在的陈列室外，还可以监视与它所在的陈视它所在的陈列室外，还可以监视与它所在的陈列室相邻的上、下、左、右列室相邻的上、下、左、右4 个陈列室。个陈列室。 试设计一个安排警卫机器人哨位的算法，使试设计一个安排警卫机器人哨位的算法，使得名画陈列馆中每一个陈列室都在警卫机
2、器人的得名画陈列馆中每一个陈列室都在警卫机器人的监视之下，且所用的警卫机器人数最少。监视之下，且所用的警卫机器人数最少。问题描述问题描述基本思想基本思想 设陈列馆由设陈列馆由m*nm*n个陈列室组成个陈列室组成, ,因为不存在重复监因为不存在重复监视，所以很多情况下都无解，我们采用的做法是根据视，所以很多情况下都无解，我们采用的做法是根据 m m和和n n的值进行分类讨论。首先，先比较的值进行分类讨论。首先，先比较m m、n n大小，使大小，使 m m始终大于始终大于n n，方面程序书写。，方面程序书写。 分三种情况讨论：分三种情况讨论： n n1 1 这时可以直接写出最优解：这时可以直接写出
3、最优解： 当当m mod 3m mod 31 1时，将哨位置于（时，将哨位置于（1 1，3k3k1 1）；）； 当当m mod 3m mod 30 0或或2 2时，将哨位置于（时，将哨位置于（2 2，3k3k2 2），），其中其中k k0 0、1 1、【、【m/3m/3】。】。 n n2 2 这种情形下必须这种情形下必须2 2端分别设置端分别设置2 2个哨位，他们个哨位，他们各监视三个陈列室。那么当各监视三个陈列室。那么当m m为偶数时问题就无解了。为偶数时问题就无解了。 当当m m为奇数时，将哨位分别至于（为奇数时，将哨位分别至于（1 1，4k4k3 3）和（）和（2 2，4k4k1 1），
4、），k k0 0、1 1、【、【m/4m/4】。】。 n2 n2 容易验证容易验证 当当n n3 3，m m3 3和和n n3 3，m m4 4时无解，时无解，n n4 4，m m4 4有解。有解。 设置哨位时，允许在的设置哨位时，允许在的n n1 1行和行和m m1 1列设置哨位，但列设置哨位，但不要求的第不要求的第n n1 1行和行和m m1 1列陈列室受到监视，那么当列陈列室受到监视，那么当n=3n=3且且m=5m=5时在不重复监视下有解那么时在不重复监视下有解那么n n3 3，m m5 5的不可重复的不可重复监视问题一定有解。但是通过验证监视问题一定有解。但是通过验证n n3 3，m
5、m5 5的不可重复的不可重复监视哨位设置问题无解，那么当监视哨位设置问题无解，那么当n=3n=3且且m=5m=5时在不重复监时在不重复监视下无解。视下无解。 通过以上讨论就将所有情况分析完全了，简单写一个通过以上讨论就将所有情况分析完全了，简单写一个包含多个条件判断的程序就可以实现该算法。包含多个条件判断的程序就可以实现该算法。哪里不懂，点哪里哪里不懂，点哪里?#include#includeusingnamespacestd;usingnamespacestd;voidmain()voidmain() intn,m,k;intn,m,k;coutcout设陈列馆由设陈列馆由m*nm*n个陈列
6、个陈列室组成室组成, ,请分别输入请分别输入mm和和n:endl;n:endl;coutn=;coutn;cinn;coutm=;coutm;cinm;if(nm)if(nm)k=n;k=n;n=m;n=m;m=k;m=k;if(n=1)if(n=1) if(m%3=0)if(m%3=0)k=m/3;k=m/3;elseelsek=m/3+1;k=m/3+1; elseelse if(n=2)if(n=2)if(m%2=1)k=(m-3)/2+2;if(m%2=1)k=(m-3)/2+2;elseelsecoutNoSolution!;k=0;coutNoSolution!;k=0;if(k!=0)if(k!=0)coutkendlcoutkendl; ;system(pause);system(pause); elseelseif(n=3)if(n=3)coutNoSolution!;k=0;cout=3&m=5)if(n=3&m=5)coutNoSolution!;k=0;coutNoSolution!;k=0; 验证n=1时当当m mod 3m mod 31 1当当m mod 3m mod 30 0或或2 2谢谢！谢谢！
