世界名画陈列馆问题

《世界名画陈列馆问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、世界名画陈列馆问题(不重复监视)主讲人：张伟海世界名画陈列馆由m×n个排列成矩形阵列的陈列室组成。为了防止名画被盗，需要在陈列室中设置警卫机器人哨位。每个警卫机器人除了监视它所在的陈列室外，还可以监视与它所在的陈列室相邻的上、下、左、右4个陈列室。试设计一个安排警卫机器人哨位的算法，使得名画陈列馆中每一个陈列室都在警卫机器人的监视之下，且所用的警卫机器人数最少。★问题描述基本思想设陈列馆由m*n个陈列室组成,因为不存在重复监视，所以很多情况下都无解，我们采用的做法是根据m和n的值进行分类讨论。首先，先比较m、n大小，使m始终大于n，方面程序书写。分三种情况讨论：n＝1这时

2、可以直接写出最优解：当mmod3＝1时，将哨位置于（1，3k＋1）；当mmod3＝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的不可重复

3、监视问题一定有解。但是通过验证n＝3，m＝5的不可重复监视哨位设置问题无解，那么当n>=3且m>=5时在不重复监视下无解。通过以上讨论就将所有情况分析完全了，简单写一个包含多个条件判断的程序就可以实现该算法。哪里不懂，点哪里?#includeusingnamespacestd;voidmain(){intn,m,k;cout<<"设陈列馆由m*n个陈列室组成,请分别输入m和n:"<>n;cout<<"m=";cin>>m;if(n>m){k=n;n=m;m=k;}if(n==1){if(m%3==0)k=m/3

4、;elsek=m/3+1;}else{if(n==2){if(m%2==1)k=(m-3)/2+2;else{cout<<"NoSolution!";k=0;}}if(k!=0)cout<=3&&m>=5){cout<<"NoSolution!";k=0;}}}}验证n=1时当mmod3＝1当mmod3＝0或2谢谢！