参考链接：poj2870Light Up(迭代加深搜索)_ophunter的专栏-CSDN博客
一?说明：
1.1?题目大致意思是：放置灯以照亮整个矩阵，返回所需灯的最小数量。
?????????给定一个矩阵如图(a)所示，其中黑色方框表示障碍物，障碍物的编号表示其周围需要的灯的数量(无编号的障碍物所需的灯数不限)；除此之外，空白网格所在行列也需要有灯存在，以便于照亮该空白网格。
1.2?由于涉及寻找所有方案，所以确定本题用DFS解决。
1.2.1?将问题分解为两级DFS：
? ? ? ? 第一级：以障碍物所需灯数为目标，寻找所有“照亮障碍物“”的安灯方案
? ? ? ? 第二级：对第一级结果中的每一个方案进行安灯，以“照亮剩余的空白网格”。
? ? ? ? 因此，两级方案所需的最小灯数，即为答案。
1.2.2 设计原理及注意事项
## 0 程序设计时，用不同数值的元素值反映各个信息：
????????空白用-10表示，
????????照亮后的行、列空白用-20表示，
????????点灯位置赋值为-30。
## 1 编号为0的障碍物的4邻域为禁区，不能放置灯；
## 2 以编号最大的障碍物的邻接点为初始顶点，进行DFS搜索；
## 3 对当前障碍物的邻点放置灯时，该灯周围如果有其他障碍物，也将被照亮；
## 4 本题分为2级DFS：第一级，为障碍物点灯，寻找所有可行的方案；第二级，对各个可行方案中的空白点灯
## 4.1 在确定障碍物的点灯方案后，当对空白网格进行点灯时，灯的周围不能有障碍物，否则将使得障碍物的点灯方案有误。
## 4.1.1 如果为空白网格点灯时，其周围存在障碍物，则将该位置赋值为-100；再继续对其他空白进行点灯，直到无-10存在。最后，判断是否有-100，无-100说明点灯成功。
# # 5. 终止条件
# # 第一级dfs：所有障碍物的所需点灯均已安装完毕
# # 第二级dfs:? 所有空白格均已点灯完毕
# # 6?本程序需要查询所有方案，不能使用return True or False，而是使用 return。
1.2.3 其他注意事项：
1.3?关键问题在于实施细节。
1.3.1 本人用了整整3天才做完。太菜了。代码超长。
1.3.2?我觉得应该绘制一个思维导图，用于呈现本题的程序流程，否则数天之后，本人将不记得这程序的设计逻辑。
1.4?思维导图有点可怕：
1.4.1?总图
?1.4.2?
查看PDF吧，实在是太庞大了。
POJ-2870LightUp+DFS(1级DFS+1级DFS)+Python-思维导图-互联网文档类资源-CSDN下载
1.4.3?或许应该写成Word文档。
二?代码实现
# poj2870Light Up(迭代加深搜索)
# https://blog.csdn.net/ophunter_lcm/article/details/9318079?locationNum=10&fps=1&utm_medium=distribute.pc_relevant.none-task-blog-2~default~baidujs_title~default-0.no_search_link&spm=1001.2101.3001.4242.1
## 结果正确，但是，太耗时了。考虑，将重复的方案去掉。
##
# 试一试吧 20211221 2108
## 0 程序设计时，用不同大小的元素值反映各个信息：空白用-10表示，照亮后的行。列空白用-20表示，点灯位置赋值为-30。
## 1 编号为0的障碍物的邻域为禁区，不能放置灯
## 2 以编号最大的障碍物的邻接点为初始顶点，进行DFS搜索
## 3 对当前障碍物的邻点放置灯时，该灯周围如果有其他障碍物，也将被照亮
## 4 本题分为2级DFS：第一级，为障碍物点灯，寻找所有可行的方案；第二级，对各个可行方案中的空白点灯
## 4.1 在确定障碍物的点灯方案后，当对空白网格进行点灯时，灯的周围不能有障碍物，否则将使得障碍物的点灯方案有误。
## 4.1.1 如果为空白网格点灯时，其周围存在障碍物，则将该位置赋值为-100；再继续对其他空白进行点灯，直到无-10存在。最后，判断是否有-100，无-100说明点灯成功。
# 5. 终止条件
# # 第一级dfs：所有障碍物的所需点灯均已安装完毕
# # 第二级dfs:所有空白格均已点灯完毕
# 6 需要查询所有方案的时候，应该不能使用return True or False，而是使用 return
# # 一些约束条件：
# 1. 障碍旁边的灯的个数与其编号相同
# 2. 同一行或列最多是有一个灯，即已经被点亮的地方，不能再放置灯
# 3. 所有的空白均被照亮
# 4. 灯可以照亮未被障碍堵塞的整行或整列
# 8 迭代返回和终止的条件是什么？
import collections
import math
#1.1 数据转化
# 1.1 注意障碍数是否为0
# 1.2 注意将障碍的横纵坐标均减去1，再进行赋值
def sub2Dict(RR,CC,B_num,B_data):
##
subData = [[-10]*CC for i in range(RR)] # # # 空白用-10表示
## 1 将障碍添加到数据矩阵中，同时获得障碍矩阵
Barrier_dict = collections.defaultdict(list)
if B_num > 0:
for bi in range(B_num):
rr,cc,kk = map(int,B_data[bi].strip().split(' '))
subData[rr-1][cc-1] = kk # 横纵坐标减去1，使之从下表0开始编号
# Barrier_dict[kk] = [str(rr-1)+';'+str(cc-1),rr-1,cc-1,kk] # 坐标索引，横坐标、纵坐标、所需的灯数 # 隐患：只保存一次-1障碍，本字典记录的障碍数小于实际数
Barrier_dict[str(rr - 1) + ';' + str(cc - 1)] = [str(rr - 1) + ';' + str(cc - 1), rr - 1, cc - 1, kk]
## 将数据转化为dict
Data_dict = collections.defaultdict(list)
Stop_dict = collections.defaultdict(list) # 需要提前设置该空值
for ri in range(RR):
for ci in range(CC):
# 0 获得元素坐标
Data_dict[str(ri)+';'+str(ci)] = subData[ri][ci]
## 1 查找编号为0的元素的邻域，它的空位置领域，不能放置灯，即得到禁区的坐标
if subData[ri][ci] == 0:
Stop_dict = ForNeibs(ri, ci, RR, CC, subData)
return subData,Data_dict,Stop_dict,Barrier_dict
## 查找节点的可用邻域
def ForNeibs(ri,ci,RR,CC,subData):
Neib_Dict = collections.defaultdict(list)
## 查找当前节点的有效的4邻域，且只有其为空格时才属于有效的潜在置灯位置
## 是否加入，不属于禁区呢？
if 0 <= ri + 1 <= RR - 1 and subData[ri + 1][ci] == -10:
node1 = str(ri + 1) + ';' + str(ci)
Neib_Dict[node1] = [subData[ri + 1][ci]]
if 0 <= ri - 1 <= RR - 1 and subData[ri - 1][ci] == -10:
node1 = str(ri - 1) + ';' + str(ci)
Neib_Dict[node1] = [subData[ri - 1][ci]]
if 0 <= ci + 1 <= CC - 1 and subData[ri][ci + 1] == -10:
node1 = str(ri) + ';' + str(ci + 1)
Neib_Dict[node1] = [subData[ri][ci + 1]]
if 0 <= ci - 1 <= CC - 1 and subData[ri][ci - 1] == -10:
node1 = str(ri) + ';' + str(ci - 1)
Neib_Dict[node1] = [subData[ri][ci - 1]]
return Neib_Dict
## 查找节点的可用邻域
def ForNeibs2(ri,ci,RR,CC,subData,stop_keys):
Neib_Dict = collections.defaultdict(list)
## 查找当前节点的有效的4邻域，且只有其为空格时才属于有效的潜在置灯位置
## 是否加入，不属于禁区呢？
if 0 <= ri + 1 <= RR - 1 and subData[ri + 1][ci] == -10 and str(ri + 1) + ';' + str(ci) not in stop_keys:
node1 = str(ri + 1) + ';' + str(ci)
Neib_Dict[node1] = [subData[ri + 1][ci]]
if 0 <= ri - 1 <= RR - 1 and subData[ri - 1][ci] == -10 and str(ri - 1) + ';' + str(ci) not in stop_keys:
node1 = str(ri - 1) + ';' + str(ci)
Neib_Dict[node1] = [subData[ri - 1][ci]]
if 0 <= ci + 1 <= CC - 1 and subData[ri][ci + 1] == -10 and str(ri) + ';' + str(ci + 1) not in stop_keys:
node1 = str(ri) + ';' + str(ci + 1)
Neib_Dict[node1] = [subData[ri][ci + 1]]
if 0 <= ci - 1 <= CC - 1 and subData[ri][ci - 1] == -10 and str(ri) + ';' + str(ci - 1) not in stop_keys:
node1 = str(ri) + ';' + str(ci - 1)
Neib_Dict[node1] = [subData[ri][ci - 1]]
return Neib_Dict
##
class Solution:
def DFS(self):
# 2 获得禁区字典
temp = []
for stop_keys in Stop_dict.keys():
temp.append(stop_keys)
self.stop_keys = temp
# 3 获得障碍区字典
temp = []
temp2 = []
for barrier_keys in Barrier_dict.keys():
temp.append(barrier_keys)
temp2.append(Barrier_dict[barrier_keys][3])
self.barrier_keys = temp
##
##1 以障碍区的编号数为基准进行第一轮搜索
self.keys_queue = sorted(set(temp2), reverse=True) # 降序排列
if -1 in set(self.keys_queue): # 则不考虑-1障碍周围的灯数
self.keys_queue = self.keys_queue[:-1]
## 判断长度是否为0
if len(self.keys_queue) == 0: # 即没有任何障碍
return min(RR, CC)
elif len(self.keys_queue) > 0:
## 这里新设置一个障碍字典，用来存放以“障碍序号”为键值的障碍信息，其中不包括编号为-1的障碍
new_Barrier_dict = collections.defaultdict(list)
for ki in Barrier_dict.keys():
if Barrier_dict[ki][3] in self.keys_queue:
new_Barrier_dict[Barrier_dict[ki][3]] = Barrier_dict[ki]
# if 0 not in set(self.keys_queue): # 当不存在0障碍时，则不能使用禁区字典Stop_dict
# Stop_Flag = False
# subData,Data_dict,Stop_dict,Barrier_dict
## 开始处理：
## 以编号最大的障碍的可用邻域作为初始点，分别计算各初始点情况下，所能获得的最小值。
node = self.keys_queue[0]
node_rr, node_cc = new_Barrier_dict[node][1], new_Barrier_dict[node][2] # 当前障碍点的坐标
Neib_Dicts = ForNeibs(node_rr, node_cc, RR, CC, subData) # 当前障碍点的可用的邻域
self.waysOFbarrier = []
self.lampsOFwys = []
# ans_step = [math.inf]
if len(Neib_Dicts)>= new_Barrier_dict[node][3]:# 说明可以放置灯
for ni in Neib_Dicts.keys(): # 4邻域中的可用坐标点
# 判断是否不位于禁区
if ni not in self.stop_keys: # 不位于禁区
# 0 设置所需灯数的初始值
self.Barrier_lamps = math.inf # 障碍灯数
# 1 获得当前的坐标
ni_rr, ni_cc = map(int, ni.strip().split(';'))
Init_lamps = []
# Flag,steps = self.dfs(node,ni_rr,ni_cc,subData, Data_dict,new_Barrier_dict, Init_lamps)
self.dfs(ni_rr, ni_cc, subData, new_Barrier_dict, Init_lamps)
# ans_step.append(self.Max_lamps)
# 这里应该存储并比较dfs的返回结果
# Flag表示当前的节点下，是否存在可行的方案
# steps表示当前节点下，可能方案的灯数。
else:
# 说明不足以放置所需数目的灯
return math.inf
## 接下来，再对获得方案进行第二轮dfs处理，实现对所有空格的点亮
##
ANS_steps = []
Len_ans = len(self.waysOFbarrier)
## 剔除重复方案
Ans_ways_set = set()
# Ans_ways_set.add('None')
Ans_ways_final = []
Ans_ways_lampa = []
Ans_ways_index = []
for ai in range(Len_ans):
# 转化为一维数组
zl_series = ''
for si in range(RR):
for sj in range(CC):
zl_series = zl_series + str(self.waysOFbarrier[ai][si][sj])
zl = zl_series
if zl not in Ans_ways_set:
Ans_ways_set.add(zl_series)
Ans_ways_final.append(self.waysOFbarrier[ai])
Ans_ways_lampa.append(self.lampsOFwys[ai])
Ans_ways_index.append(ai)
Len_ans = len(Ans_ways_final)
for ai in range(Len_ans):
# 获得方案结果和已经点亮的灯数
new_Data = Ans_ways_final[ai]
Cur_Barrier_lamps = Ans_ways_lampa[ai]
# #1 获得空位置的节点：
empty_dict = self.FindEmpty(new_Data)
self.Max_lamps = math.inf
if len(empty_dict) == 0:# 为0则终止
if self.Max_lamps > Cur_Barrier_lamps+0:
self.Max_lamps = Cur_Barrier_lamps + 0
ANS_steps.append(self.Max_lamps)
break # 进行下一次循环
else:
empty_step = [math.inf]
for keyy in empty_dict.keys(): # 循环对每个节点进行分析，查找这些方案下能获得的最小的灯数
self.Max_empty_steps = math.inf
ni_rr, ni_cc = map(int, keyy.strip().split(';')) # 获得当前节点的坐标
Init_empty_lamps = []
self.dfs2(ni_rr, ni_cc,new_Data,empty_dict,Init_empty_lamps)
empty_step.append(self.Max_empty_steps)
##
# zl = min(empty_step)
if Cur_Barrier_lamps + min(empty_step) < self.Max_lamps :
self.Max_lamps = Cur_Barrier_lamps + min(empty_step)
ANS_steps.append(self.Max_lamps)
return min(ANS_steps)
# def dfs(self,parent_node,ni_rr,ni_cc,Data,data_dict,barrier_dict,lamps):
def dfs(self, ni_rr, ni_cc, Data, barrier_dict, lamps):
# （一）
## 用于存放错误的点灯位置
# Error_lams = []
## 0 传递数据，存储灯的位置
new_lamps = []
## 0.1 存储当前该灯的位置
lamp_str = str(ni_rr) + ';' + str(ni_cc);
if lamp_str not in self.stop_keys:
new_lamps.append(lamp_str) ## 首先加入一个新元素
else:
return False,0
for lap in lamps: # 继承原来的灯
if lap not in self.stop_keys:
new_lamps.append(lap) ## 然后再逐个加入
## 0 传递数据
new_Data = self.Render(ni_rr, ni_cc, Data)
# ## 0 传递字典数据；用来更新障碍周围所需的灯数
new_barrier_dict = {}
for keyi in barrier_dict.keys():
new_barrier_dict[keyi] = barrier_dict[keyi][::]
# 照亮周围的障碍物
# 当前节点的四邻域
Lit_Flag,new_barrier_dict = self.LitupBarrier(ni_rr, ni_cc, RR, CC, new_barrier_dict)
if Lit_Flag == False: # 说明点灯失败
return
# new_barrier_dict[parent_node][3] = new_barrier_dict[parent_node][3] - 1;
#### 能否在此处进行判断呢？
# （二）
## 判断一下是否终止了：判断障碍周围是否已经放置了所需数据的灯
Lamp_needed = True
for barri in self.keys_queue:
if new_barrier_dict[barri][3] != 0:
Lamp_needed = False
break
if Lamp_needed == True: # 说明障碍物旁边的所需灯已经放置完毕，接下来需要对其他的空白节点进行放置
## 当前终止之后，还要再嵌套一个dfs用来填充之后的-10空格，知道矩阵中再无-10元素
## 当前所需的灯的数量
LEN = len(new_lamps)
if self.Barrier_lamps > LEN:
self.Barrier_lamps = LEN
#####
self.waysOFbarrier.append(new_Data) # 这里坑死我了，不应该有缩进的，否则有些可能的方案不能保存。
self.lampsOFwys.append(self.Barrier_lamps)
# return True,self.Barrier_lamps
return # 这里也不要有缩进了。
## 循环分析
for node in self.keys_queue:
if node != max(self.keys_queue):
if new_barrier_dict[node+1][3] !=0: # 说明未找到合适的方案 // 加入这条判断，有助于加速，避免获得重复的方案。
return
node_rr, node_cc = new_barrier_dict[node][1], new_barrier_dict[node][2] # 当前障碍点的坐标
# 获得当前障碍的候选点灯节点
Neib_Dicts = ForNeibs(node_rr, node_cc, RR, CC, new_Data) # 当前障碍点的可用的邻域
if len(Neib_Dicts) == new_barrier_dict[node][3] and new_barrier_dict[node][3]>0 : # 说明可以放置灯
for ni in Neib_Dicts.keys(): # 4邻域中的可用坐标点
# 判断是否不位于禁区
if ni not in self.stop_keys:
if ni not in new_lamps: # 不位于禁区，并且未被点亮
# 获得当前的坐标
ni_rr, ni_cc = map(int, ni.strip().split(';'))
# 判断当前行列中，是否存在已点亮的灯，如果有的话，说明之前的这个灯放错了，应该记录下来，在递归返回时，将其位置恢复原状，并添加到禁止访问区域中
Error_lams = self.D_ErrorL(ni_rr, ni_cc,new_lamps)
if len(Error_lams)>0:## 如果存在冲突，则返回
return
# for ei in Error_lams:
# self.stop_keys.append(ei) # 不能添加进来，因为这有可能是错误方案导致的。
# 将每个点填充到数据中
## 这里设置一个程序，将灯所在行列全部赋值-20（被遮挡的区域除外）
new_Data = self.Render(ni_rr, ni_cc,new_Data)
## 存储该灯的位置
# new_lamps = []
new_lamps.append(str(ni_rr) + ';' + str(ni_cc))
# 记录已点的灯数
Lit_Flag, new_barrier_dict = self.LitupBarrier(ni_rr, ni_cc, RR, CC, new_barrier_dict)
if Lit_Flag == False: # 说明点灯失败
return
# new_barrier_dict[node][3] = new_barrier_dict[node][3] -1; # 每点灯一次，其所需灯数少1
else:
# return False, 0
return
elif len(Neib_Dicts) < new_barrier_dict[node][3] and new_barrier_dict[node][3] >0:
# return False, 0
# 说明无法获得满足需求的灯，直接结束吧！
return
elif len(Neib_Dicts) > new_barrier_dict[node][3] and new_barrier_dict[node][3]>0: # 当需要点灯，并且有可用的点灯区域时
# 这里需要迭代处理吧
for ni in Neib_Dicts.keys(): # 4邻域中的可用坐标点
# 判断是否不位于禁区
if ni in self.stop_keys:# 有位于禁区的邻点，不符合要求，寻找下一个
continue
else: # 需要迭代处理吗
# 获得当前的坐标
ni_rr, ni_cc = map(int, ni.strip().split(';'))
## 这里需要判断：
# 1. 何时更新新的灯队列（建议在进入循环之后判断）
# 2. 何时判断，当前行列中是否已经有灯了（建议此时判断）
Error_lams = self.D_ErrorL(ni_rr, ni_cc, new_lamps)
if len(Error_lams)>0:
break # 说明此时ni所在行或列已经有灯了，不再进行后续处理
else:
## 接下来应该要进入递归循环了
self.dfs(ni_rr, ni_cc, new_Data, new_barrier_dict, new_lamps)
return
## 设计第二个dfs
def dfs2(self,ni_rr, ni_cc, Data, empty_dict,lamps):
# 1 传递数据，并存储当前灯的位置
new_lamps = []
str1 = str(ni_rr)+';'+str(ni_cc)
if str1 not in self.stop_keys:
new_lamps.append(str1) ## 首先加入当前的新元素
else:
return
for lap in lamps: # 继承原来的灯
if lap not in self.stop_keys:
new_lamps.append(lap) ## 然后再逐个加入
# 2 传递，并更新当前的数据
# 2.1 特别注意：当前行列不能有其他灯
# 2.2 照亮整行和整列，除非遇到障碍物(在本例中，只要连续地遇到-10、-20，就照亮；遇到其他元素，就停止照亮)
new_Data = self.Render2(ni_rr, ni_cc, Data)
# 2.3 进一步判断，如果当前点的4邻域有已编号的障碍物，则不能点亮
# 3 获得新的空格坐标
new_empty_dict = self.FindEmpty(new_Data)
# 3.1 如果为空，则终止
if len(new_empty_dict) == 0: # 说明已经没有-10空位置了，但不说明成功了，因为有些点可能不能用来点亮，被设置成了-100
# 1 检查是否存在-100 元素
# 1.1 转成一串数组
zl_series = set()
for si in range(RR):
for sj in range(CC):
zl_series.add(new_Data[si][sj])
# 1.2 判断是否有-100
if -100 in zl_series:
self.Max_empty_steps = math.inf
return
else:
# 说明全部已经点亮
if len(new_lamps) < self.Max_empty_steps:
self.Max_empty_steps = len(new_lamps)
return
##
else:
# 进入下一次循环
## 检测空位置：
for ei in new_empty_dict.keys():
ei_rr, ei_cc = map(int, ei.strip().split(';')) # 获得当前节点的坐标
self.dfs2(ei_rr, ei_cc,new_Data,new_empty_dict,new_lamps)
return
## 照亮空格
## 检测当前点灯的位置周围是否存在有编号的障碍物
def Render2(self, ni_rr, ni_cc, Data):
# 首先，使用该方法将原始矩阵赋值给新矩阵
new_Data = []
for rr in range(len(Data)):
temp = []
for cc in range(len(Data[0])):
temp.append(Data[rr][cc])
new_Data.append(temp)
## 1 检测当前点灯的位置周围是否存在有编号的障碍物
if self.decteBarrier(ni_rr, ni_cc) == False: # False:表示有障碍物
# 则将其赋值为-100，并返回
new_Data[ni_rr][ni_cc] = -100
return new_Data
else:
#
## 1 点亮当前行的各列元素
for ci in range(ni_cc, CC):
if new_Data[ni_rr][ci] == -10 or new_Data[ni_rr][ci] == -20 or new_Data[ni_rr][ci] == -100:
new_Data[ni_rr][ci] = -20; # 点亮，即赋值为-20
else:
break # 遇到其他元素则终止点亮
for ci in range(ni_cc, -1, -1):
if new_Data[ni_rr][ci] == -10 or new_Data[ni_rr][ci] == -20 or new_Data[ni_rr][ci] == -100:
new_Data[ni_rr][ci] = -20; # 点亮，即赋值为-20
else:
break # 遇到其他元素则终止点亮
## 2 点亮当前列的各行元素
for ri in range(ni_rr, RR):
if new_Data[ri][ni_cc] == -10 or new_Data[ri][ni_cc] == -20 or new_Data[ri][ni_cc] == -100:
new_Data[ri][ni_cc] = -20; # 点亮，即赋值为-20
else:
break # 遇到其他元素则终止点亮
for ri in range(ni_rr, -1, -1):
if new_Data[ri][ni_cc] == -10 or new_Data[ri][ni_cc] == -20 or new_Data[ri][ni_cc] == -100:
new_Data[ri][ni_cc] = -20; # 点亮，即赋值为-20
else:
break # 遇到其他元素则终止点亮
## 返回点亮后的元素
new_Data[ni_rr][ni_cc] = -30
return new_Data
## 这个解决方案可能存在问题。
def decteBarrier(self,ri,ci):
Neib_Dict = []
if 0 <= ri + 1 <= RR - 1:
node1 = str(ri + 1) + ';' + str(ci)
Neib_Dict.append(node1)
if 0 <= ri - 1 <= RR - 1:
node1 = str(ri - 1) + ';' + str(ci)
Neib_Dict.append(node1)
if 0 <= ci + 1 <= CC - 1:
node1 = str(ri) + ';' + str(ci + 1)
Neib_Dict.append(node1)
if 0 <= ci - 1 <= CC - 1:
node1 = str(ri) + ';' + str(ci - 1)
Neib_Dict.append(node1)
## 判断是否有障碍物
for bi in Barrier_dict.keys():
if Barrier_dict[bi][0] in Neib_Dict and Barrier_dict[bi][3] !=-1: # 说明当前点的周围有障碍物，且障碍物有编号，因此不能点灯
return False
return True
## 查找空格
def FindEmpty(self,new_Data):
empty_dict = collections.defaultdict(list)
for rr in range(RR):
for cc in range(CC):
if new_Data[rr][cc] == -10:
str1 = str(rr)+';'+str(cc)
empty_dict[str1] = [str1,rr,cc]
return empty_dict
## 当前节点的四邻域，是否存在障碍物
def LitupBarrier(self,ri, ci, RR, CC,new_barrier_dict):
# 对当前的点灯位置进行分析，判断其周围是否有障碍
# 如果周围有障碍0，则返回错误
# 对于编号大于0的障碍，均减去1，并且减1之后，不能为负数
Neib_Dict = []
if 0 <= ri + 1 <= RR - 1:
node1 = str(ri + 1) + ';' + str(ci)
Neib_Dict.append(node1)
if 0 <= ri - 1 <= RR - 1:
node1 = str(ri - 1) + ';' + str(ci)
Neib_Dict.append(node1)
if 0 <= ci + 1 <= CC - 1:
node1 = str(ri) + ';' + str(ci + 1)
Neib_Dict.append(node1)
if 0 <= ci - 1 <= CC - 1:
node1 = str(ri) + ';' + str(ci - 1)
Neib_Dict.append(node1)
## 对每个障碍进行分析
for bi in new_barrier_dict:
if new_barrier_dict[bi][0] in Neib_Dict: # 如果当前障碍位于点灯邻域内
if new_barrier_dict[bi][3] != 0: # 如果不等于0，则将所需灯数减1
new_barrier_dict[bi][3] = new_barrier_dict[bi][3] - 1
else:# 如果等于0，说明当前方案又去
return False, {}
return True,new_barrier_dict
## 这里设置一个程序，将灯所在行列全部赋值-20（被遮挡的区域除外）
def Render(self,ni_rr, ni_cc,Data):
# 填充所在行和所在列的元素
new_Data = []
for rr in range(len(Data)):
temp = []
for cc in range(len(Data[0])):
temp.append(Data[rr][cc])
new_Data.append(temp)
##1 查找当前行是否存在阻碍
Cs_little = [0]
Cs_large = [math.inf]
for bi in self.barrier_keys: # 与障碍区域进行比较
bi_r, bi_c = map(int,bi.split(';'))#Barrier_dict[bi][1], Barrier_dict[bi][2]
if bi_r == ni_rr:
if ni_cc>bi_c:
Cs_little.append(bi_c+1)
else:
Cs_large.append(bi_c-1)
start_c = max(0,max(Cs_little))
end_c = min(CC-1,min(Cs_large))
for ic in range(CC):
if start_c<=ic<=end_c:
new_Data[ni_rr][ic] = -20 #点亮之后，编程-20
##2 查找当前列是否存在阻碍
Rs_little = [0]
Rs_large = [math.inf]
for bi in self.barrier_keys: # 与障碍区域进行比较
bi_r, bi_c = map(int, bi.split(';')) # Barrier_dict[bi][1], Barrier_dict[bi][2]
# bi_r, bi_c = Barrier_dict[bi][1],Barrier_dict[bi][2]
if bi_c == ni_cc:
if ni_rr > bi_r:
Rs_little.append(bi_r+1)
else:
Rs_large.append(bi_r-1)
start_r = max(0, max(Rs_little))
end_r = min(RR-1, min(Rs_large))
for ir in range(RR):
if start_r <= ir <= end_r:
new_Data[ir][ni_cc] = -20 # 点亮之后，编程-20
## 特别地
new_Data[ni_rr][ni_cc] = -30 #点灯的位置用-30表示
return new_Data
# # 判断当前行列中，是否存在已点亮的灯，
def D_ErrorL(self,ni_rr, ni_cc, new_lamps):
Error_lams = []
# 特殊情况，此时不存在点灯冲突
if len(new_lamps) == 0:
return Error_lams
else:
# 检测是否存在点灯冲突
for lamp in new_lamps: # 对于已经点灯的点进行分析
l_r,l_c = map(int,lamp.split(';'))
# 对于同一行而言，判断两者之间是否有障碍
if ni_rr == l_r:
Flag_r = False # 用于标记两者之间是否有阻碍
for bi in self.barrier_keys:# 与障碍区域进行比较
bi_r,bi_c = map(int,bi.split(';'))
if bi_r == ni_rr:
if min(ni_cc,l_c)<bi_c<max(ni_cc,l_c):
# 说明没问题
Flag_r = True
break
if Flag_r == False: # 说明两者之间没有阻碍，有误
Error_lams.append(str(l_r)+';'+str(l_c))
# 对于同一列而言，判断两者之间是否有障碍
if ni_cc == l_c:
Flag_c = False # 用于标记两者之间是否有阻碍
for bi in self.barrier_keys:
bi_r, bi_c = map(int, bi.split(';'))
if bi_c == ni_cc:
if min(ni_rr, l_r) < bi_r < max(ni_rr, l_r):
# 说明没问题
Flag_c = True
break
if Flag_c == False: # 说明两者之间没有阻碍，有误
Error_lams.append(str(l_r)+';'+str(l_c))
return Error_lams
## 迎接输入
data_size = []
barrier_num = []
barrier_data = []
while True:
##
N,M = map(int,input().strip().split())
if N==0 and M==0:
break
else:
data_size.append([N,M])
##
temp_num = int(input().strip())
barrier_num.append(temp_num)
temp = []
for ni in range(temp_num):
temp.append(input().strip())
barrier_data.append(temp)
# print(barrier_data)
## 数据提取
case_num = len(data_size)
for case in range(case_num):
#1 提取的数据
RR,CC = data_size[case][0],data_size[case][1] # 数据矩阵的长宽
B_num = barrier_num[case]
B_data = barrier_data[case]
#1.1 数据转化
subData,Data_dict,Stop_dict,Barrier_dict = sub2Dict(RR,CC,B_num,B_data)
# print(subData)
# print(dict)
## 接下来，需要设计方法进行dfs搜索了：查找所有可行的方案，并返回满足要求的最少灯数。
test = Solution()
ans = test.DFS()
if ans < math.inf:
print(ans)
else:
print("No solution")
输入：
2 2
0
2 2
1
2 2 1
6 7
7
2 3 -1
3 3 0
4 2 1
5 4 3
5 6 2
1 7 -1
6 5 -1
0 0输出：
2
No solution
8