参考资料：POJ 1691 - Painting A Board | 眈眈探求
一 题目描述：
? ? ? ? 给定一个矩形区域，它包含多个不重叠的方块，现在要给各方块涂颜色，并且设定了各方块的目标颜色，例如A的目标颜色为蓝色，B的为红色。
? ? ? ? 着色原则：
? ? ? ? ? ? ? ? *1?假设为C着色，那么必须保证其上方的格子A已被涂色，否则C不能被着色；也就是说，必须从低行号开始着色，而不能反向。
? ? ? ? ? ? ? ? *2?当为A着色之后，考虑其他与A具有相同颜色的方块是否满足*1的着色条件，如果满足，则将其同时着色。例如，与A具有相同颜色的方块包括C、E、F，那么，在给A着色之后，C满足着色条件，也将被同时着色。
? ? ? ? ? ? ? ? *3?接下来，考虑未着色的其他方格，从上到下，进行着色。
? ? ? ? ? ? ? ? *4?要求寻找一种方案，使得涂满所有方格的次数最少。
二?解题原则：
1.?首先，要将数据转化为矩阵数据：
1.1?根据输入数据，确定矩阵的行、列尺寸
1.2?根据输入数据，确定各矩形框的信息：
label_dict[label_i] = [i,[rr_s,cc_s,rr_e,cc_e],label_c,False,[above,under]] # 矩形参数——区域标签:区域编号+区域坐标+区域颜色+是否着色标记+[上方矩形集合、下方矩形集合]2?以左上角顶点行号为0的矩形为初始节点，进行DFS搜索
2.1?获得当前矩形的颜色
2.1.1?获得具有相同颜色的矩形区域列表，并按左上角顶点行号从小到大排序（因为着色的顺序是从上到下，对应于行号从小到大。）
2.2?对具有相同颜色的矩形进行着色
# 1. 判断其上方是否为空，或者已经全部着色：
# 1.1 是：则进行着色
3?检测尚未着色的区域，按左上角顶点行号升序排列之后，进行DFS递归处理
4?如果所有矩形均已着色完毕，则结束返回。
三?代码实现
# http://poj.org/problem?id=1691
import math
## 数据处理子程序需要确定横纵坐标的最大值
def proData(rec_Data,rec_num):
# 将数据转化为矩阵
## 首先获得矩阵的长宽信息
temp_r=[]
temp_c = []
for i in range(rec_num):
temp_r.append(rec_Data[i][2])
temp_c.append(rec_Data[i][3])
RR = max(temp_r)
CC = max(temp_c)
## 更新矩形坐标信息
new_rec_Data = []
for i in range(rec_num):
# 共5个元素：坐标1 + 坐标2 + 颜色
## 将坐标2的横纵坐标均减1，转化为矩阵坐标，便于后续索引
temp = []
for j in range(5):
if j ==2 or j ==3:
temp.append(rec_Data[i][j]-1)
else:
temp.append(rec_Data[i][j])
new_rec_Data.append(temp)
# 建立空矩阵，用于存放数据
## 建立组别数据和颜色数据
data_group = [[0]*CC for i in range(RR)]
# data_color = [[0] * CC for i in range(RR)]
label_dict = {}
# 赋值组别数据
for i in range(rec_num):
# 获得区域标志
label_i = rec_label[i]
# 获得第i的矩形区域及颜色
rr_s,cc_s = new_rec_Data[i][0],new_rec_Data[i][1]
rr_e,cc_e = new_rec_Data[i][2],new_rec_Data[i][3]
label_c = new_rec_Data[i][4]
# 存储区域字典信息
label_dict[label_i] = [i,[rr_s,cc_s,rr_e,cc_e],label_c,False] # 区域标签:区域编号+区域坐标+区域颜色+是否着色标记
# 赋值组别数据
for g_i in range(rr_s,rr_e+1,1):
for g_j in range(cc_s,cc_e+1,1):
data_group[g_i][g_j] = label_i
# data_color[g_i][g_j] = label_c
# 存放起始节点和终止节点
start_nodes = []
end_nodes = []
# 获取每个矩形区域的上下组别信息
for label_i in label_dict.keys():
# 获取矩形区域的坐标
rr_s, cc_s = label_dict[label_i][1][0],label_dict[label_i][1][1]
rr_e, cc_e = label_dict[label_i][1][2],label_dict[label_i][1][3]
# 获取其第1行以上和最后一行以下各列对应的组别
if rr_s-1>=0:
above_set = set(data_group[rr_s-1][cc_s:cc_e+1])
above = []
while len(above_set)>0:
above.append(above_set.pop())
else:
above = []
# 添加到起始节点列表中
start_nodes.append(label_i)
if rr_e+1<=RR-1:
under_set = set(data_group[rr_e+1][cc_s:cc_e+1])
under = []
while len(under_set) > 0:
under.append(under_set.pop())
else:
under = []
end_nodes.append(label_i)
# 存储信息
label_dict[label_i].append([above,under]) # 存储当前矩形的上方矩形和下方矩形
return data_group,label_dict,start_nodes,end_nodes
## 执行DFS处理
class Solution:
def DFS(self):
# 利用DFS查询可行方案中的最小步数
## 设定初始步数为无穷大
self.Init_steps = math.inf
# 依次以各个初始节点为起点，进行DFS搜索
for node in start_nodes:
step = 1 # 步数计数
self.dfs(node,label_dict,step)
return self.Init_steps
def dfs(self,node,label_dict,step):
## 首先转存字典数据
new_label_dict = {}
for key in label_dict.keys():
new_label_dict[key] = label_dict[key][::]
##
##
# 具体处理：
#1 当前标签的颜色
color = label_dict[node][2] #
# 1.1 获得具有相同颜色的所有标签，并按行号从小到大排序（因为着色的顺序是从上到小，对应于行号从小到大。）
Same_color_rec_uLr = [] # 相同颜色区域标签
for key in new_label_dict.keys():
if new_label_dict[key][2] == color:# 颜色相同者
# 存储其左上角顶点的横坐标
Same_color_rec_uLr.append([key,new_label_dict[key][1][0]]) # 左上角顶点的横坐标 + 标签
Same_color_rec_uLr = sorted(Same_color_rec_uLr,key=lambda s: s[1]) # 升序排列;存储具有相同颜色区域标签
## 1.2 对具有相同颜色的矩形进行着色处理
for zl_i in range(len(Same_color_rec_uLr)):
node_i = Same_color_rec_uLr[zl_i][0]
if new_label_dict[node_i][3] == True:# 如果已经着色，则循环至下一节点
continue
else:
# 1 判断是否对当前矩形区域进行着色
# 1. 判断其上方是否为空，或者已经全部着色：
# 1.1 是：则进行着色，
# 取出其上方的节点，判断其是否着色
above_node = new_label_dict[node_i][4][0] # 取出其上方矩形的着色标志
if len(above_node) == 0: # 如果上方为空，则可以着色
# 可以进行着色
new_label_dict[node_i][3] = True
else:
Flagg = True
for n_i in above_node:
if new_label_dict[n_i][3] == False: # 如果当前节点的上方存在未着色情况，则不允许对该节点着色
Flagg = False
break
if Flagg == True: # 说明其上方节点均已经着色，可以对该节点进行着色
new_label_dict[node_i][3] = True
#2 检测尚未着色的区域，按行号升序排列之后，进行DFS递归处理
new_new_label_dict = {}
unColor_rec_uLr = [] # 存储未着色表区域及左上角行号，便于排序
for keyi in new_label_dict.keys():
if new_label_dict[keyi][3] == False:# 并未着色
new_new_label_dict[keyi] = new_label_dict[keyi][::] #转存未着色的矩形信息
unColor_rec_uLr.append([keyi, new_label_dict[keyi][1][0]]) # 左上角顶点的横坐标 + 标签
unColor_rec_uLr = sorted(unColor_rec_uLr, key=lambda s: s[1]) # 升序排列;用于排列DFS着色的优先顺序，即：从上到下着色
#2.1 首先判断是否均已着色
if len(unColor_rec_uLr) == 0:
# 说明均已经着色完毕
if self.Init_steps > step:
self.Init_steps = step
#
return
else:
## 对未着色的节点，按行号从上到下开始处理
for zl_i in range(len(unColor_rec_uLr)):
# 取出当前节点
new_node = unColor_rec_uLr[zl_i][0]
self.dfs(new_node,new_label_dict,step+1)
return # 已经设计了优先顺序，当前获得的方案是唯一的，不需要再进行全局搜索
return
# 首先，获得数据输入
data = []
rec_nums = []
# case数目
N = int(input().strip())
for case in range(N):
# 1 当前case包含的矩形数量
rec_n = int(input().strip())
rec_nums.append(rec_n)
# 2 各矩形的坐标
temp = []
for rec_i in range(rec_n):
temp.append(list(map(int,input().strip().split(' '))))
data.append(temp)
# print(data)
## 对各组数据进行处理
## 提前设定各矩形的标号
rec_label = {0:'A',1:'B',2:'C',3:'D',4:'E',5:'F',6:'G',7:'H',8:'I',9:'J',10:'K',11:'L',12:'M',13:'N',14:'P'}
for case in range(N):
# 获得矩形数据及数量
rec_Data = data[case]
rec_num = rec_nums[case]
# 数据预处理
data_group,label_dict,start_nodes,end_nodes = proData(rec_Data,rec_num)
# print(label_dict)
## 执行DFS搜索
test = Solution()
ans = test.DFS()
print(ans)
输入：
描述：
The first line of the input file contains an integer M which is the number of test cases to solve (1 <= M <= 10). For each test case, the first line contains an integer N, the number of rectangles, followed by N lines describing the rectangles. Each rectangle R is specified by 5 integers in one line: the y and x coordinates of the upper left corner of R, the y and x coordinates of the lower right corner of R, followed by the color-code of R.
1
7
0 0 2 2 1
0 2 1 6 2
2 0 4 2 1
1 2 4 4 2
1 4 3 6 1
4 0 6 4 1
3 4 6 6 2输出：
3