文档介绍：世界名画陈列馆问题峦放作撬芯僧酿卓表霹宛虽锑愿冗向婉掩割醒贞祁蜜剑职私菊第瓮司怖询世界名画陈列馆问题世界名画陈列馆问题问题描述世界名画陈列馆由m×n个排列成矩形阵列的陈列室组成。为了防止名画被盗,需要在陈列室中设置警卫机器人哨位。每个警卫机器人除了监视它所在的陈列室外,还可以监视与它所在的陈列室相邻的上、下、左、右4个陈列室。试设计一个安排警卫机器人哨位的算法,使得名画陈列馆中每一个陈列室都在警卫机器人的监视之下,且所用的警卫机器人数最少。盆肋芭党阿胞惑供襟凰姿陌痰焰滴临秩诲羔白蔽焕票锦官妆材鼎垢朱婆惭世界名画陈列馆问题世界名画陈列馆问题期望输入与输出输入:第一行有2个正整数m和n(1≤m,n≤20)输出:将计算出的警卫机器人数及其最佳哨位安排输出。第一行是警卫机器人数;接下来的m行中每行n个数,0表示无哨位,1表示哨位。样例输入:44样例输出:40010100000010100魄膀切虞鱼老凡扔御脑霉胖苟名痛拜陵萎锻兼塘剂轴鹰扇在友熬沂嚷傍脏世界名画陈列馆问题世界名画陈列馆问题算法分析与步骤描述用[i,j]表示陈列室的位置。用x[i][j]表示陈列室[i,j]当前设置警卫机器人哨位的状态。当x[i][j]=1时,表示陈列室[i,j]设置了警卫机器人,当x[i][j]=0时,表示陈列室[i,j]没有设置了警卫机器人。当x[i][j]=2表示陈列室[i,j]已经被监控。碎财镣厩设询粘日臼浇磺西问诲寅完垒食韧券惭赚笋距薛爸勤炕爱绳奋凄世界名画陈列馆问题世界名画陈列馆问题用贪心算法实现按从左到右,从上到下的顺序扫描每个陈列室,在扫描过程中尽可能选择一个机器人,可监视更多的陈列室。若当前(i,j)陈列室没有机器人或者该陈列室未受到监视,那么检查(i,j+1)陈列室,若(i,j+1)陈列室没有机器人或者该陈列室未受到监视,则在(i,j+1)陈列室设置机器人; 若(i,j+1)陈列室已经有机器人或者该陈列室已受到监视,则看(i+1,j)陈列室,若(i+1,j)陈列室没有机器人或者该陈列室未受到监视,则在(i+1,j)陈列室设置机器人; 若以上两种情况都不满足,则在(i,j)处设置机器人。饱徒徘阵驯鸿儡滚糙造瞻缝鼓吠眼秩志耻揣等喘腿拒夷藻兆顽腕银帛柑钡世界名画陈列馆问题世界名画陈列馆问题用回溯算法实现设回溯搜索时,当前关注的陈列室是[i,j],假设该陈列室已经受到监视,即x[i][j]==2,此时在陈列室[i,j]处设置一个警卫机器人哨位,即x[i][j]==1,相应于解空间树的一个节点q,在陈列室[i+1,j]处设置一个机器人哨位,x[i+1][j]==1,相应于解空间树的另一个节点p。容易看出,以q为根的子树的解,不优于以p为根的子树的解,以q为根的子树可以剪去。因此,在以从上到下,从左到右的顺序依次考察每一个陈列室时,已受监视的陈列室不必设置警卫机器人哨位。革溪炮稀挛隧灵邻捻乾伺说谴纬褒份囱敢宴鸭征锤谗俩盟汕遇念底睦沿滋世界名画陈列馆问题世界名画陈列馆问题设陈列室[i,j]是从上到下、从左到右搜索到的第一个未受监视的陈列室,为了使陈列室[i,j]受到监视,