M3537.填充特殊网格

dfs, https://leetcode.cn/problems/fill-a-special-grid/

给你一个非负整数 N，表示一个 $2^{N} \times 2^{N}$ 的网格。你需要用从 0 到 $2^{2 N} - 1$ 的整数填充网格，使其成为一个特殊网格。一个网格当且仅当满足以下所有条件时，才能称之为特殊网格：

右上角象限中的所有数字都小于右下角象限中的所有数字。
右下角象限中的所有数字都小于左下角象限中的所有数字。
左下角象限中的所有数字都小于左上角象限中的所有数字。
每个象限也都是一个特殊网格。

返回一个 $2^{N} \times 2^{N}$ 的特殊网格。

注意：任何 1x1 的网格都是特殊网格。

示例 1：

输入： N = 0

输出： [[0]]

解释：

唯一可以放置的数字是 0，并且网格中只有一个位置。

示例 2：

输入： N = 1

输出： [[3,0],[2,1]]

解释：

每个象限的数字如下：

右上角：0
右下角：1
左下角：2
左上角：3

由于 0 < 1 < 2 < 3，该网格满足给定的约束条件。

示例 3：

输入： N = 2

输出： [[15,12,3,0],[14,13,2,1],[11,8,7,4],[10,9,6,5]]

解释：

每个象限的数字如下：

右上角：3, 0, 2, 1
右下角：7, 4, 6, 5
左下角：11, 8, 10, 9
左上角：15, 12, 14, 13
max(3, 0, 2, 1) < min(7, 4, 6, 5)
max(7, 4, 6, 5) < min(11, 8, 10, 9)
max(11, 8, 10, 9) < min(15, 12, 14, 13)

这满足前三个要求。此外，每个象限也是一个特殊网格。因此，这是一个特殊网格。

提示：

0 <= N <= 10

可以递归地构造这个“特殊网格”，遵循题目中描述的象限递增顺序：

象限编号（以左上为原点）：
- Q1（右上） 最小的数。
- Q2（右下） 比 Q1 的数都大。
- Q3（左下） 比 Q2 的数都大。
- Q4（左上） 最大的一组。
每一个象限本身也必须是一个特殊网格，因此递归地构造即可。

关键点：

每次我们把一个 2^N x 2^N 的网格，拆分成 4 个 2^{N-1} x 2^{N-1} 的子网格，然后分别递归生成这 4 个子网格。

我们将递归返回的 4 个子网格（大小相同）按照如下顺序拼接：

Q4 | Q1
-------
Q3 | Q2

这样在拼接时，保证了：

Q1 < Q2 < Q3 < Q4

同时通过给每个象限加上不同的偏移量（offset）来保证整体单调递增。

✅ 实现代码如下：

python

from typing import List

class Solution:
    def specialGrid(self, N: int) -> List[List[int]]:
        def build(n: int, base: int) -> List[List[int]]:
            if n == 0:
                return [[base]]
            
            size = 2 ** (n - 1)
            block = 4 ** (n - 1)  # 子网格大小
            
            # 构建 4 个象限
            q1 = build(n - 1, base + block * 0)  # 右上
            q2 = build(n - 1, base + block * 1)  # 右下
            q3 = build(n - 1, base + block * 2)  # 左下
            q4 = build(n - 1, base + block * 3)  # 左上
            
            # 拼接成大的网格
            upper = [q4[i] + q1[i] for i in range(size)]
            lower = [q3[i] + q2[i] for i in range(size)]
            return upper + lower
        
        return build(N, 0)

这行代码：

python

block = 4 ** (n - 1)

实际上是在计算每个象限子网格中元素的数量，用于给每个象限分配一个正确的偏移量（base）。

🔍 解释：

对于一个 2^n x 2^n 的网格，它总共有：

$(2^{n})^{2} = 4^{n}$

个元素。

如果你把它分成 4 个象限（每个象限大小为 2^{n-1} x 2^{n-1}），那么每个象限有：

$(2^{n} - 1)^{2} = 4^{n} - 1$

个元素。我们就需要这个值来正确偏移每个象限的起始数值。

✅ 举个例子：

假设 N = 2：

整个网格是 4x4，总共 4^2 = 16 个数。
每个子网格大小是 2x2，即 4^{2-1} = 4 个数。
那么我们给四个象限分配数字区间为：
- Q1（右上）：起始值 base + 0 * 4 = 0
- Q2（右下）：起始值 base + 1 * 4 = 4
- Q3（左下）：起始值 base + 2 * 4 = 8
- Q4（左上）：起始值 base + 3 * 4 = 12

✅ 总结：

python

block = 4 ** (n - 1)

这句代码是为了计算每个子网格中包含的元素数量，从而正确设置每个象限的起始 base，确保：

所有数字都是连续的、不重复的。
每个象限都比上一个象限的大（因为偏移量是递增的）。

如果你觉得 4 ** (n - 1) 不直观，你也可以用：

python

block = (2 ** (n - 1)) ** 2

这两者是等价的。

M3537.填充特殊网格 ​

M3537.填充特殊网格