from typing import List
from functools import lru_cache
from typing import List
class DlxPreciseOvelap:
# max_node_num是节点池的大小,取1节点大小即可, row_num和col_num是矩阵的行数和列数
# one_points是1节点的坐标的二元组(ii, jj)的列表,行坐标和列坐标都是从1开始(注意不是从0开始)
def __init__(self, max_node_num, row_num, col_num, one_points: List):
max_node_num += col_num+1 # 加上哨兵的节点数
self.__row_num = row_num
self.__col_num = col_num
self.__pos = 0 # 当前空闲的末尾位置
# 上下左右后继的节点id
self.uu, self.dd, self.ll, self.rr = [0]*max_node_num, [0]*max_node_num, [0]*max_node_num, [0]*max_node_num
self.row, self.col = [0] * max_node_num, [0] * max_node_num # 节点的行和列
self.one_num = [0] * (self.__col_num + 1) # 列上的1计数值
self.one_points = one_points
# 十字链表状态初始化
def __boot(self):
one_points = self.one_points
one_points.sort()
# 最上面一行0号节点到col_num号节点都是哨兵, 都是链表头,不是实际1节点,0号节点下面不会接其他节点,只作为是横向的哨兵
uu, dd, ll, rr = self.uu, self.dd, self.ll, self.rr
col_num = self.__col_num
for jj in range(col_num + 1):
ll[jj] = jj - 1
rr[jj] = jj + 1
uu[jj] = jj
dd[jj] = jj
ll[0], rr[col_num] = col_num, 0
self.__pos = col_num + 1
# 逐行添加节点
i = 0
n = len(one_points)
row, col, one_num = self.row, self.col, self.one_num
while i < n:
j = i
h_node = None # 一行的第一个节点
while j < n and one_points[j][0] == one_points[i][0]:
ii, jj = one_points[j]
pos = self.__pos
row[pos], col[pos] = ii, jj
one_num[jj] += 1
uu[pos], dd[pos] = jj, dd[jj]
uu[dd[jj]] = pos
dd[jj] = pos
# 新节点总是放在头节点的右边
if h_node is None:
h_node = pos
ll[h_node], rr[h_node] = h_node, h_node
else:
ll[pos], rr[pos] = h_node, rr[h_node]
ll[rr[h_node]] = pos
rr[h_node] = pos
j += 1
self.__pos += 1
i = j
# 删除下标是c的列
def __remove_col(self, c):
uu, dd, ll, rr = self.uu, self.dd, self.ll, self.rr
one_num = self.one_num
row, col, one_num = self.row, self.col, self.one_num
# 横向把竖直方向的链表断开
ll[rr[c]] = ll[c]
rr[ll[c]] = rr[c]
node = dd[c]
while node != c:
# 把c列上数值是1的行上的节点全部在数值方向删掉,因为c这一列上的节点已经整条链都断开了,c列不用重复删了
nn = rr[node]
while nn != node:
one_num[col[nn]] -= 1
dd[uu[nn]] = dd[nn]
uu[dd[nn]] = uu[nn]
nn = rr[nn]
node = dd[node]
# 恢复下标是c的列
def __resume_col(self, c):
uu, dd, ll, rr = self.uu, self.dd, self.ll, self.rr
one_num = self.one_num
row, col, one_num = self.row, self.col, self.one_num
node = uu[c]
while node != c:
nn = ll[node]
while nn != node:
dd[uu[nn]] = nn
uu[dd[nn]] = nn
one_num[col[nn]] += 1
nn = ll[nn]
node = uu[node]
# 竖直方向的链表接回去
rr[ll[c]] = c
ll[rr[c]] = c
# dfs找第一个可行解
def __dfs1(self, path: List):
uu, dd, ll, rr = self.uu, self.dd, self.ll, self.rr
one_num = self.one_num
row, col, one_num = self.row, self.col, self.one_num
if rr[0] == 0:
return True
# 选可选的行最少的列
min_one_num = 0x7fffffff
min_col = None
c = rr[0]
while c != 0:
if one_num[c] < min_one_num:
min_one_num = one_num[c]
min_col = c
c = rr[c]
self.__remove_col(min_col)
# 枚举要在min_col列放1的行
node = dd[min_col]
while node != min_col:
# 当前选择了的行中所有数值是1的列相当于都已经在这一行放了1了,所以都删除, 不用再在这些列上枚举方案了
nn = rr[node]
while nn != node:
self.__remove_col(col[nn])
nn = rr[nn]
path.append(row[node])
if self.__dfs1(path):
return True
# 恢复
path.pop()
nn = ll[node]
while nn != node:
self.__resume_col(col[nn])
nn = ll[nn]
node = dd[node]
self.__resume_col(min_col)
return False
# 返回任意一个可行解,不保证行数最小, 返回行号的列表[row1, row2, ......]
@lru_cache(typed=False, maxsize=1) # 为了这个函数能重复调用,这里使用caches
def get_one_feasible_solution(self):
self.__boot()
ans = []
if self.__dfs1(ans):
return ans
return None
#-------------- 下面一段是准备工作 -------------------
# 4 * 4 的图形左右对称
def mirror(img: List[str]):
ret = []
for line in img:
ret.append(line[::-1])
return ret
# 旋转90度
def rotate(img: List[str]):
img = mirror(img)
m = [[None] * 4 for _ in range(4)]
for i in range(4):
for j in range(4):
m[i][j] = img[3-j][3-i]
ret = []
for line in m:
ret.append(''.join(line))
return ret
images = [
[
"** ",
"* ",
" ",
" "
],
[
"****",
" ",
" ",
" "
],
[
"*** ",
"* ",
" ",
" "
],
[
"** ",
"** ",
" ",
" "
],
[
"* ",
"* ",
"*** ",
" "
],
[
"****",
" * ",
" ",
" "
],
[
"*** ",
"* * ",
" ",
" "
],
[
"*** ",
"** ",
" ",
" "
],
[
"*** ",
" **",
" ",
" "
],
[
" * ",
"*** ",
" * ",
" "
],
[
"* ",
"** ",
" ** ",
" "
],
[
"****",
"* ",
" ",
" "
],
]
# 获取图形中占用的位置,以左上角为(0, 0)标准位置求出所有占用位置的相对坐标
def get_pos(img: List[str]):
min_ii = 0x7fffffff
min_jj = 0x7fffffff
for i in range(4):
for j in range(4):
if img[i][j] != ' ':
min_ii = min(min_ii, i)
min_jj = min(min_jj, j)
ans = []
for i in range(4):
for j in range(4):
if img[i][j] != ' ':
ans.append((i - min_ii, j - min_jj))
return tuple(ans)
# 构造所有可能的摆法
pos_info = set()
for idx in range(len(images)):
img1 = mirror(images[idx])
t = images[idx]
pos_info.add((idx, get_pos(t)))
for i in range(3):
t = rotate(t)
pos_info.add((idx, get_pos(t)))
t = img1
pos_info.add((idx, get_pos(t)))
for i in range(3):
t = rotate(t)
pos_info.add((idx, get_pos(t)))
grid = []
for i in range(10):
grid.append(input())
used_id = set()
for line in grid:
for ch in line:
if ch != ' ':
used_id.add(ord(ch) - ord('A'))
img_info = [] # ( 0-11的字符编号,占用字符的位置列表 )
for i in range(0, 10):
for j in range(0, i+1):
for idx, pos_tuple in pos_info:
# 已经出现在图形中的字符筛掉
if idx in used_id:
continue
t = []
flag = True
for ii, jj in pos_tuple:
iii, jjj = ii+ i, jj + j
if iii < 0 or iii >= 10 or jjj < 0 or jjj >= 10 or jjj > iii or grid[iii][jjj] != '.':
flag = False
break
t.append((iii, jjj))
if flag:
img_info.append((idx, tuple(t)))
arr = [
[1],
[2, 3],
[4, 5, 6],
[7, 8, 9, 10],
[11, 12, 13, 14, 15],
[16, 17, 18, 19, 20, 21],
[22, 23, 24, 25, 26, 27, 28],
[29, 30, 31, 32, 33, 34, 35, 36],
[37, 38, 39, 40, 41, 42, 43, 44, 45],
[46, 47, 48, 49, 50, 51, 52, 53, 54, 55]
]
# 特征1表示摆法占用的位置编号,1到55共55个
def get_feature1_idx_list(info):
_, pos_tuple = info
ret = []
for ii, jj in pos_tuple:
ret.append(arr[ii][jj])
return ret
# 特征2表示图形是否已经被使用 图形总共12种
def get_feature2_idx(info):
id, _ = info
return 56 + id
one_points = []
row = 1
row2info = {}
# 没有出现在图形中的零件构造行
for info in img_info:
pos = get_feature1_idx_list(info)
pos.append(get_feature2_idx(info))
row2info[row] = ( chr(ord('A') + info[0]), info[1] )
for col in pos:
one_points.append((row, col))
row += 1
# 已经出现在图形中的零件构造行
mm = {}
for i in range(10):
for j in range(i+1):
if grid[i][j] != '.':
if grid[i][j] not in mm:
mm[grid[i][j]] = []
mm[grid[i][j]].append((i, j))
for ch, pos_list in mm.items():
id = ord(ch) - ord('A')
pos = get_feature1_idx_list((id, tuple(pos_list)))
pos.append(get_feature2_idx((id, tuple(pos_list))))
row2info[row] = ( ch, pos_list )
for col in pos:
one_points.append((row, col))
row += 1
# DLX精确覆盖求解,并还原图形
algo = DlxPreciseOvelap(len(one_points), row-1, 12 + 55, one_points)
ret = algo.get_one_feasible_solution()
ans = [[''] * 10 for _ in range(10)]
if ret is None:
print("No solution")
else:
for row in ret:
ch, pos_list = row2info[row]
for ii, jj in pos_list:
ans[ii][jj] = ch
for line in ans:
print(''.join(line))