文档介绍：世界名画陈列馆问题 Page ?2 问题描述?世界名画陈列馆由 m×n个排列成矩形阵列的陈列室组成。为了防止名画被盗,需要在陈列室中设置警卫机器人哨位。每个警卫机器人除了监视它所在的陈列室外,还可以监视与它所在的陈列室相邻的上、下、左、右 4 个陈列室。?试设计一个安排警卫机器人哨位的算法,使得名画陈列馆中每一个陈列室都在警卫机器人的监视之下,且所用的警卫机器人数最少。 Page ?3 期望输入与输出?输入:?第一行有 2 个正整数 m和 n (1 ≤ m,n ≤ 20) ?输出: ?将计算出的警卫机器人数及其最佳哨位安排输出。第一行是警卫机器人数;接下来的 m行中每行 n个数, 0 表示无哨位, 1 表示哨位。?样例输入: ? 4 4 ?样例输出: ?4 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 Page ?4 算法分析与步骤描述?用[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] 已经被监控。 Page ?5 用贪心算法实现按从左到右,从上到下的顺序扫描每个陈列室,在扫描过程中尽可能选择一个机器人,可监视更多的陈列室。若当前( 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)处设置机器人。 Page ?6 用回溯算法实现?设回溯搜索时,当前关注的陈列室是[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为根的子树可以剪去。因此,在以从上到下,从左到右的顺序依次考察每一个陈列室时,已受监视的陈列室不必设置警卫机器人哨位。 Page ?7 ?设陈列室[i,j] 是从上到下、从左到右搜索到的第