文档介绍：世界名画陈列馆问题墅氦魄圆划甘读栓钡令犀本仙撩库姜即祥述殆汤耪润人群沃掏擞整涵仔胸世界名画陈列馆问题世界名画陈列馆问题问题描述世界名画陈列馆由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]受到监视,