Leetcode 3311. Construct 2D Grid Matching Graph Layout

Leetcode 3311. Construct 2D Grid Matching Graph Layout
- 1. 解题思路
- 2. 代码实现

题目链接：3311. Construct 2D Grid Matching Graph Layout

1. 解题思路

这一题看起来搞定的人不多，不过多半是因为繁琐吧。

这道题思路上其实非常的直接，就是一个递归的方法，我们可以从连接关系当中快速地找到所有的角节点，边节点以及内部节点，然后通过角节点和边节点，我们可以还原出矩阵的4条边，然后通过内部节点我们可以使用递归的方法求得其构成的内部矩阵，最后我们将得到的4条边拼接到内部矩阵的外侧即可。

整体来说，我们可以将函数抽象为4步：

找出所有的角节点，边节点以及内部节点
还原矩阵的边
计算内部矩阵
将2中计算得到的边拼接到3中得到的内部矩阵外侧

每一步其实都没有特别复杂，但是会有一些特殊情况，多少会有些复杂和繁琐。比如说：

找角节点，边节点以及内部节点的时候，通常情况下其度数分别为2、3、4，不过如果矩阵仅一行，那么其对应的度数就是1、2、3，而如果矩阵仅一个点，那么其度数只有1。
还原矩阵的边的时候，通常矩阵有4条边，每条边除端节点之外均为边节点，且相互间不关联。但是如果矩阵只有1行或者两行，上述说法就会有一点问题，需要单独考虑一下。
如果矩阵只有1行或者两行，那么他是没有内部矩阵的，因此我们直接对齐矩阵的边然后返回即可；
拼接矩阵的边的时候，需要首先对齐找到矩阵的4条边的上下左右位置关系，然后进行拼接。

Anyway，总之就是实现上比较复杂，但是整体难度不大，有兴趣的读者可以试试，没兴趣的话这道题pass我觉得也没啥……

2. 代码实现

给出python代码实现如下：

class Solution:def constructGridLayout(self, n: int, edges: List[List[int]]) -> List[List[int]]:def classify_points(points, edges):graph = defaultdict(list)for u, v in edges:graph[u].append(v)graph[v].append(u)cnt = min(len(graph[u]) for u in points)corners = {u for u in points if len(graph[u]) == cnt}sides = {u for u in points if len(graph[u]) == cnt+1}inners = {u for u in points if len(graph[u]) == cnt+2}return graph, corners, sides, innersdef construct_grid_sides(graph, corners, sides):if len(sides) == 0:u = list(corners)[0]grid_sides = [[u, graph[u][0]]]if len(graph[u]) > 1:v = graph[u][1]w = [i for i in graph[v] if i != u][0]grid_sides.append([v, w])return grid_sideselif any(u in corners for c in corners for u in graph[c]):u = list(corners)[0]v = [i for i in graph[u] if i in corners][0]unext = [i for i in graph[u] if i != v][0]vnext = [i for i in graph[v] if i != u][0]grid_sides = [[u, unext], [v, vnext]]u, v = unext, vnextwhile True:unext = [i for i in graph[u] if i != grid_sides[0][-2] and i != v]vnext = [i for i in graph[v] if i != grid_sides[1][-2] and i != u]if len(unext) == 0:breakgrid_sides[0].append(unext[0])grid_sides[1].append(vnext[0])u, v = unext[0], vnext[0]else:grid_sides = []u0 = list(corners)[0]for u in graph[u0]:side = [u0, u]v = [i for i in graph[u] if i in sides and i != side[-2]]while v:u = v[0]side.append(u)v = [i for i in graph[u] if i in sides and i != side[-2]]u = [i for i in graph[u] if i in corners and i != side[-2]][0]side.append(u)grid_sides.append(side)v = [i for i in graph[u] if i != side[-2]]if v:v = v[0]side = [u, v]u = vv = [i for i in graph[u] if i in sides and i != side[-2]]while v:u = v[0]side.append(u)v = [i for i in graph[u] if i in sides and i != side[-2]]u = [i for i in graph[u] if i in corners and i != side[-2]][0]side.append(u)grid_sides.append(side)return grid_sidesdef merge_grid(graph, grid_sides, inner_grid):lu, ld, ru, rd = inner_grid[0][0], inner_grid[-1][0], inner_grid[0][-1], inner_grid[-1][-1]for side in grid_sides:if lu in graph[side[1]] and ru in graph[side[-2]]:up = sidebreakif lu in graph[side[-2]] and ru in graph[side[1]]:up = side[::-1]breakfor side in grid_sides:if side[0] == up[0] and side[-1] != up[-1]:left = sidebreakif side[-1] == up[0] and side[0] != up[-1]:left = side[::-1]breakfor side in grid_sides:if side[0] == up[-1] and side[-1] != up[0]:right = sidebreakif side[-1] == up[-1] and side[0] != up[0]:right = side[::-1]breakfor side in grid_sides:if side[0] == left[-1] and side[-1] == right[-1]:down = sidebreakif side[-1] == left[-1] and side[0] == right[-1]:down = side[::-1]breakgrid = [up] + [[l] + side + [r] for l, side, r in zip(left[1:-1], inner_grid, right[1:-1])] + [down]return griddef construct(points, edges):if len(points) <= 1:return [list(points)]graph, corners, sides, inners = classify_points(points, edges)grid_sides = construct_grid_sides(graph, corners, sides)if len(inners) == 0:return grid_sidesinner_edges = [[u, v] for u, v in edges if u in inners and v in inners]inner_grid = construct(inners, inner_edges)grid = merge_grid(graph, grid_sides, inner_grid)return gridpoints = [i for i in range(n)]return construct(points, edges)