做导航网站成本,wap网站生成app,seo推广经验,广西省建设厅网站世界名画--陈列馆问题 问题描述python解答位操作python代码 问题描述
哨兵布置问题。一个展馆由mn个矩阵阵列的陈列室组成#xff0c;需要在陈列室中设立哨位#xff0c;每个哨位上的哨兵除了可以监视自己所在陈列室外#xff0c;还可以监视他上、下、左、右四个陈列室需要在陈列室中设立哨位每个哨位上的哨兵除了可以监视自己所在陈列室外还可以监视他上、下、左、右四个陈列室给出一个最佳哨位安排方法使得所有陈列室都在监视之下但使用的哨兵最少。
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] *( n2) for _ in range (m2)]# 被监视的房间位置self.room_watched [[0] * (n2) for _ in range (m2)]# (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] * (n2) for _ in range (m2)]# 初始化room_watched数组全为0node.room_watched [[0] * (n2) for _ in range (m2)]# 当前点在i1,j1node.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)看不懂吧小老弟
就是遍历每一行的所有情况判断最小的灯泡数量 其实灯泡也就是哨兵的意思 同时照亮和监控是一个道理
解读连接大概如下 尽量调试代码从代码入手你就会懂
