世界名画--陈列馆问题

本文主要是介绍世界名画--陈列馆问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

世界名画--陈列馆问题

问题描述
- python解答
- - 位操作python代码

问题描述

哨兵布置问题。一个展馆由m×n个矩阵阵列的陈列室组成，需要在陈列室中设立哨位，每个哨位上的哨兵除了可以监视自己所在陈列室外，还可以监视他上、下、左、右四个陈列室，给出一个最佳哨位安排方法，使得所有陈列室都在监视之下，但使用的哨兵最少。

python解答

from queue import PriorityQueue# m*n的房间
m, n = 0, 0
# 自身和上下左右5个方位
position = [(0, 0), (0, 1), (0, -1), (1, 0), (-1, 0)]
# 最优结果 ans为机器人个数 ans_arr为每个机器人的位置
ans_arr = [[0] * 30 for _ in range (30)]
ans = 0class Node:def __init__(self):# 机器人位置self.robot_position = [[0] *( n+2) for _ in range (m+2)]# 被监视的房间位置self.room_watched = [[0] * (n+2) for _ in range (m+2)]# (i,j)为当前遍历到的坐标self.i, self.j = 1, 1# 机器人数   被监视的房间个数self.robotNum, self.roomNum = 0, 0def __lt__(self, other): # 定义比较运算符，按照灯泡数量从大到小排序return self.roomNum > other.roomNum # 返回比较结果# 优先队列，cmp函数会自动执行
q = PriorityQueue ()def init(node):# 初始化robot_position数组全为0node.robot_position = [[0] * (n+2) for _ in range (m+2)]# 初始化room_watched数组全为0node.room_watched = [[0] * (n+2) for _ in range (m+2)]# 当前点在i=1,j=1node.i, node.j = 1, 1# 当前的机器人数；当前的监控房间数node.robotNum, node.roomNum = 0, 0# 在博物馆的上下扩充两行for i in range (m + 2):node.room_watched[i][0] = node.room_watched[i][m + 1] = 1# 在博物馆的左右扩充两列for i in range (n + 2):node.room_watched[0][i] = node.room_watched[n + 1][i] = 1return nodedef setRobot(p, x, y):# 以下几行都是在复制一份快照pnode = Node ()node = init (node)node.i, node.j = p.i, p.jnode.roomNum = p.roomNumnode.robot_position = [row[:] for row in p.robot_position]node.room_watched = [row[:] for row in p.room_watched]# 在（x,y)点新增机器人，机器人数量要+1node.robot_position[x][y] = 1node.robotNum = p.robotNum + 1# 对这个新增机器人的上下左右和自身标记被监控for d in range (5):# pos_x,pos_y表示机器人上下左右位置，我们标记这些位置的房间被监控pos_x = x + position[d][0]pos_y = y + position[d][1]node.room_watched[pos_x][pos_y] += 1# 标记一个房间，roomNum就加一。# 一定要等于1，因为有的房间会被重复监控，那就是2了if node.room_watched[pos_x][pos_y] == 1:node.roomNum += 1# 如果行数不越界 且 当前点被监控了while node.i <= m and node.room_watched[node.i][node.j]:# 当前点的列右移一个单位node.j += 1# 如果右移之后越界了，就换行if node.j > n:node.i += 1node.j = 1# 把当前快照存到优先队列里，会调用cmp排序，保证最顶端的是最优的快照q.put ((node.robotNum, node))def main():global m, n, ans, ans_arr# 输入行列m, n = map (int, input ().split ())# 机器人最多的数量ans = m * n // 3 + 2# 初始化node = Node ()node = init (node)# 快照放入队列q.put ((node.robotNum, node))# 如果队列不空while not q.empty ():# 返回队列第一个p = q.get ()[1]# 如果房间没有全被监控，则分别在当前遍历点的下方、本身、右方放置机器人# 注意这三种情况是互不干扰的，它们会生成三种快照，判断出用机器人最少的一个if p.roomNum < m * n:# 1、在下方放置# 判断条件就是下方有位置可放，不能在最后一行）if p.i < m:setRobot (p, p.i + 1, p.j)# 2、在本身放置。# 第一个判断条件是在它已经没有下方和右方的点的情况下，只能选择自身# 第二个判断条件是它的右边没有被监控if (p.i == m and p.j == n) or p.room_watched[p.i][p.j + 1] == 0:setRobot (p, p.i, p.j)# 3、在右方放置# 第一个判断条件是遍历点右边是没被监控的点# 第二个判断条件是遍历点右边的右边是没有监控的点if p.j < n and (p.room_watched[p.i][p.j + 1] == 0 or p.room_watched[p.i][p.j + 2] == 0):setRobot (p, p.i, p.j + 1)# 如果房间全被监控了elif p.roomNum >= m * n:# 如果已安置的机器人数是目前最少的，更新结果ansif p.robotNum < ans:ans = p.robotNum# 把这种安置方法保存到结果数组ans_arr里面ans_arr = [row[:] for row in p.robot_position]# 打印结果和结果数组print (ans)for i in range (1, m + 1):for j in range (1, n + 1):print (ans_arr[i][j], end=' ')print ()if __name__ == "__main__":main ()

解读连接，大概就是三叉树的意思
只看意思，不需要看代码，他代码有错

位操作python代码

import heapq # 导入堆模块
maxn = 200 # 定义最大的矩阵大小
m, n = 0, 0 # 定义矩阵的行数和列数
ans = 0 # 定义最小的灯泡数量
ans2 = [[0] * maxn for _ in range (maxn)] # 定义一个二维数组，存储每个位置是否有灯泡class Node: # 定义一个类，表示一个状态def __init__(self, set2, loc, sum): # 定义构造函数，接收三个参数self.set2 = [row[:] for row in set2] # set2是一个二维数组，存储每个位置是否被照亮self.loc = loc # loc是当前处理的行数self.sum = sum # sum是当前使用的灯泡数量def __lt__(self, other): # 定义比较运算符，按照灯泡数量从大到小排序return self.sum > other.sum # 返回比较结果def solve(): # 定义一个函数，求解最小的灯泡数量global ans # 声明全局变量q = [] # 定义一个优先队列，存储所有可能的状态ans = 1e7 # 初始化最小的灯泡数量为一个很大的数for i in range (1 << n): # 遍历第一行的所有可能的灯泡分布j = i # 将i转换为二进制表示sum = 0 # 初始化当前使用的灯泡数量为0vis2 = [[0] * maxn for _ in range (maxn)] # 初始化一个二维数组，存储每个位置是否被照亮for s in range (1, n + 1): # 遍历第一行的每一列if j & (1 << (s - 1)): # 如果j的最低位为1，表示在该位置放置一个灯泡if vis2[1][s] == 0: # 如果该位置没有被照亮，就将其标记为1vis2[1][s] = 1if vis2[1][s - 1] == 0: # 如果该位置的左边没有被照亮，就将其标记为2vis2[1][s - 1] = 2if vis2[1][s + 1] == 0: # 如果该位置的右边没有被照亮，就将其标记为2vis2[1][s + 1] = 2if vis2[2][s] == 0: # 如果该位置的下面没有被照亮，就将其标记为2vis2[2][s] = 2sum += 1 # 灯泡数量加一j >>= 1 # 将j右移一位，继续处理下一列t = 1 # 初始化当前处理的行数为1heapq.heappush (q, Node (vis2, t, sum)) # 将当前状态加入优先队列while q: # 当优先队列不为空时，循环处理u = heapq.heappop (q) # 取出优先队列中的最优状态loc = u.loc # 获取当前状态的属性if ans <= u.sum: # 如果当前使用的灯泡数量已经大于等于最小的灯泡数量，就跳过该状态continueif u.loc == m + 1: # 如果当前处理的行数已经超过了矩阵的行数，就检查是否所有位置都被照亮flag = False # 初始化一个标志，表示是否有未被照亮的位置for i in range (1, m + 1): # 遍历矩阵的每一行for j in range (1, n + 1): # 遍历矩阵的每一列if u.set2[i][j] == 0: # 如果发现有未被照亮的位置，就将标志设为True，并跳出循环flag = Truebreakif flag: # 如果已经发现有未被照亮的位置，就跳出循环breakif flag: # 如果有未被照亮的位置，就跳过该状态continueif ans > u.sum: # 如果当前使用的灯泡数量小于最小的灯泡数量，就更新最小的灯泡数量，并复制当前的灯泡分布ans = u.sumfor i in range (maxn): # 遍历最大的矩阵大小for j in range (maxn): # 遍历最大的矩阵大小ans2[i][j] = u.set2[i][j] # 将当前状态的二维数组复制到ans2中for i in range (1, n + 1): # 遍历最后一行的每一列if ans2[m + 1][i] == 1: # 如果最后一行的下面有灯泡，就将最后一行的该位置也放置一个灯泡，并更新最小的灯泡数量ans2[m][i] = 1ans += 1sum = 0 # 初始化一个新的灯泡数量为0se2 = [[0] * maxn for _ in range (maxn)] # 初始化一个新的二维数组，存储每个位置是否被照亮for i in range (m + 1): # 复制当前状态的二维数组for j in range (maxn):se2[i][j] = u.set2[i][j]for i in range (1, n + 1): # 遍历当前处理的行数的每一列if se2[loc][i] == 0: # 如果当前位置没有被照亮，就在该位置放置一个灯泡，并更新相邻位置的照亮情况if se2[loc][i] != 1: # 如果当前位置没有被照亮，就将其标记为1se2[loc][i] = 1if se2[loc + 1][i + 1] != 1: # 如果当前位置的右上角没有被照亮，就将其标记为2se2[loc + 1][i + 1] = 2if se2[loc + 1][i - 1] != 1: # 如果当前位置的左上角没有被照亮，就将其标记为2se2[loc + 1][i - 1] = 2if se2[loc + 1][i] != 1: # 如果当前位置的上面没有被照亮，就将其标记为1se2[loc + 1][i] = 1if se2[loc + 2][i] != 1: # 如果当前位置的上上面没有被照亮，就将其标记为2se2[loc + 2][i] = 2sum += 1 # 新的灯泡数量加一heapq.heappush (q, Node (se2, u.loc + 1, sum + u.sum)) # 将新的状态加入优先队列，处理下一行if __name__ == '__main__': # 定义主函数while True: # 当输入不为0时，循环处理m, n = map (int, input ().split ()) # 读入矩阵的行数和列数if m == 0 and n == 0: # 如果行数和列数都为0，就break # 结束程序ans2 = [[0] * maxn for _ in range (maxn)] # 初始化灯泡分布为全0solve () # 调用求解函数print (ans) # 输出最小的灯泡数量flag = False # 初始化一个标志，表示是否有无解的情况if not flag: # 如果没有无解的情况，就输出灯泡分布for i in range (1, m + 1): # 遍历矩阵的每一行for j in range (1, n + 1): # 遍历矩阵的每一列if ans2[i][j] == 1: # 如果该位置有灯泡，就输出1print ("1 ", end="")else: # 否则，就输出0print ("0 ", end="")print () # 换行print () # 空行else: # 如果有无解的情况，就输出-1print ("-1")