该题解首先通过make_shapes函数将字符串形式的积木转换为整数矩阵。之后使用valid_shapes函数检验每个积木是否满足内部无空缺的条件。接着，使用Area类对每块积木进行详细的边界处理，包括边缘和角落的特征提取。valid_areas函数用于检查所有积木组成的面的角和边是否符合预设的标准。calc_merge_valids函数生成一个六维数组，存储任意两块积木在任意旋转和翻转状态下是否能够相互拼接。valid_merge_valids函数确保每块积木的每个边至少能与一块其他积木拼接。最后，Manager类中的merge_all函数尝试递归地放置所有积木，以确定是否能够完整构建立方体。
时间复杂度: O(6^2 * 4^2 * 2^2)
空间复杂度: O(6^2 * 4^2 * 2^2)
def make_shapes(shapes):
n = len(shapes[0])
mat = [[[0] * n for _ in range(n)] for _ in range(6)]
for k in range(6):
for i in range(n):
for j in range(n):
c = shapes[k][i][j]
mat[k][i][j] = int(c)
return mat
def valid_shape(shape):
n = len(shape)
for i in range(1, n - 1):
for j in range(1, n - 1):
if shape[i][j] == 0:
return False
return True
def valid_shapes(shapes):
for i in range(6):
if not valid_shape(shapes[i]):
return False
return True
class Area:
def __init__(self, mat):
self.mat = mat
self.n = len(mat)
self.edges = [None] * 4
self.corners = [None] * 4
self.make_edges()
self.make_corners()
def make_edges(self):
self.edges[0] = [self.mat[i][0] for i in range(self.n - 1, -1, -1)]
self.edges[1] = self.mat[0][::]
self.edges[2] = [self.mat[i][-1] for i in range(self.n)]
self.edges[3] = self.mat[-1][::-1]
def make_corners(self):
self.corners[0] = self.mat[-1][0]
self.corners[1] = self.mat[0][0]
self.corners[2] = self.mat[0][-1]
self.corners[3] = self.mat[-1][-1]
def cell_cnt_in_corners(self):
return sum(self.corners)
def cell_cnt_in_edges_without_corners(self):
cnt = 0
for edge in self.edges:
cnt += sum(edge)
cnt -= self.cell_cnt_in_corners() * 2
return cnt
def valid_areas(areas):
corner_cell_cnt = 0
for area in areas:
cnt = area.cell_cnt_in_corners()
corner_cell_cnt += cnt
if corner_cell_cnt != 8:
return False
n = areas[0].n
edge_cell_cnt = 0
for area in areas:
cnt = area.cell_cnt_in_edges_without_corners()
edge_cell_cnt += cnt
if edge_cell_cnt != 12 * (n - 2):
return False
return True
def calc_merge_valids(areas):
merge_valids = [[[[[[False] * 2 for _ in range(4)] for _ in range(6)] for _ in range(2)] for _ in range(4)] for _ in range(6)]
for i in range(6):
for di in range(4):
for ri in range(2):
for j in range(6):
if i == j:
continue
for dj in range(4):
for rj in range(2):
valid = calc_merge_valid(areas[i], di, ri, areas[j], dj, rj)
merge_valids[i][di][ri][j][dj][rj] = valid
for i in range(6):
for di in range(4):
for ri in range(2):
for j in range(6):
if i == j:
continue
for dj in range(4):
for rj in range(2):
assert merge_valids[i][di][ri][j][dj][rj] == merge_valids[j][dj][rj][i][di][ri]
assert merge_valids[i][di][1 - ri][j][dj][rj] == merge_valids[j][dj][rj][i][di][1 - ri]
return merge_valids
def calc_merge_valid(area0, d0, r0, area1, d1, r1):
edge0 = area0.edges[d0] if r0 == 0 else area0.edges[d0][::-1]
edge1 = area1.edges[d1] if r1 == 1 else area1.edges[d1][::-1]
return can_join(edge0, edge1)
def can_join(edge0, edge1):
n = len(edge0)
if edge0[0] + edge1[0] > 1 or edge0[-1] + edge1[-1] > 1:
return False
for i in range(1, n - 1):
if edge0[i] + edge1[i] != 1:
return False
return True
def valid_merge_valids(merge_valids):
for i in range(6):
for di in range(4):
for ri in range(2):
valid_cnt = 0
for j in range(6):
if i == j:
continue
for dj in range(4):
for rj in range(2):
valid_cnt += merge_valids[i][di][ri][j][dj][rj]
if valid_cnt == 0:
return False
return True
class Manager:
def __init__(self, merge_valids):
self.merge_valids = merge_valids
self.states = [[-1, -1, -1] for _ in range(6)]
self.edges = [[] for _ in range(12)]
self.space_edge = [[0, 1, 2, 3], [4, 5, 0, 6], [5, 7, 8, 1], [2, 8, 9, 10], [6, 3, 10, 11], [9, 7, 4, 11]]
self.space_edge_rev = [[0, 0, 0, 0], [0, 0, 1, 0], [1, 0, 0, 1], [1, 1, 0, 0], [1, 1, 1, 0], [1, 1, 1, 1]]
def merge_all(self):
self.place(0, 0, 0, 0)
areas = [1, 2, 3, 4, 5]
ans = self.try_merge(areas, 1)
return ans
def place(self, space_id, i, di, ri):
edges = self.space_edge[space_id]
pos = [(0 + di) % 4, (1 + di) % 4, (2 + di) % 4, (3 + di) % 4]
if ri:
pos[1], pos[3] = pos[3], pos[1]
placed = []
for k in range(4):
edge_id = edges[k]
dk = pos[k]
edge = self.edges[edge_id]
if len(edge) == 1:
if not self.merge_valids[edge[0][0]][edge[0][1]][edge[0][2]][i][dk][ri]:
break
placed.append(edge_id)
self.edges[edge_id].append((i, dk, ri))
return placed
def try_merge(self, areas, space_id):
if space_id == 6:
return True
for area_id in areas:
for d in range(4):
for r in range(2):
placed = self.place(space_id, area_id, d, r)
if len(placed) == 4:
new_areas = [x for x in areas if x != area_id]
ans = self.try_merge(new_areas, space_id + 1)
if ans:
return True
for i in placed:
self.edges[i].pop()
return False
class Solution:
def composeCube(self, shapes: List[List[str]]) -> bool:
shapes = make_shapes(shapes)
if not valid_shapes(shapes):
return False
areas = []
for shape in shapes:
area = Area(shape)
areas.append(area)
if not valid_areas(areas):
return False
merge_valids = calc_merge_valids(areas)
if not valid_merge_valids(merge_valids):
return False
mng = Manager(merge_valids)
if not mng.merge_all():
return False
return True