企业官网建设流程全解析

这道 3548 号题我刷到的时候，第一反应是“又一个矩阵题”，但仔细读完题面才发现事情没那么简单。等和矩阵分割，光“等和”两个字听起来像是二维前缀和的活，可题目里藏着另一个更关键的条件：分割出来的两个区域都必须连通。这就把问题从“算和”变成了“枚举连通块 + 验证补集连通”，难度直接上了一个台阶。这篇文章我就把这道困难题的完整思路、剪枝细节和调试过程写出来，给同样在啃这类题的朋友一个参考。

整道题最核心的难点在于：你不能只找出一个区域让它和等于总和的一半，你还得保证剩下的那一半也是连通的，而且两个区域是互补关系，你枚举一个区域的时候，它的补集是什么形状、连不连通，完全是动态变化的。这是典型的“约束搜索”问题，暴力枚举所有子集根本不可行，必须把搜索空间压缩到“包含某个固定点的连通块”这个范围里。

1. 题目定位与问题本质

1.1 3548 在力扣题库里是什么难度

编号到 3548 的题目，基本都是最近几个月新增的周赛压轴题，难度定在 Hard 一点也不意外。这类题目通常不是考某个单一知识点，而是把“搜索”、“剪枝”、“连通性判断”揉在一起，再加上矩阵这个载体，很容易把没有经验的人绕晕。

从刷题策略的角度讲，遇到这种编号非常新的困难题，第一件事不是急着看题解，而是先自己判断数据范围。矩阵类搜索题的复杂度通常和格子总数 n = m * n 强相关，如果 n 小于等于 20，位掩码枚举是可行的；如果 n 到 30 以上，就必须靠搜索 + 剪枝，或者深挖题目有没有特殊的数学结构。这道题核心其实就一句话：在一个矩阵里找一个连通区域，使它的和等于总和的一半，同时让补集也连通。 判断连通性是图论问题，枚举区域是组合搜索问题，两者一结合，复杂度就上来了。

1.2 问题建模：等和、连通、互补，三个条件缺一不可

先把问题用数学语言拆开。假设矩阵所有格子的和是 total，那么一个合法分割要把格子分成两个非空集合 A 和 B，满足三个条件：

• A 的所有格子之和等于 total / 2；
• B 的所有格子之和也等于 total / 2（其实 A 满足后，B 自动满足，因为总和固定）；
• A 是 4-连通的（上下左右相邻）；
• B 也是 4-连通的；
• A 和 B 的并集是整个矩阵，交集为空。

很多人在第一个条件上就翻车，忘了判断 total 的奇偶性。如果 total 是奇数，直接返回 0，因为两个区域的元素和都是整数，不可能各分到 half。这一步虽然简单，但能省掉后面所有无效搜索。

第二个需要注意的点是：A 和 B 是互补的，不是两个独立选择的区域。所以枚举的时候只需要找其中一个区域，另一个区域自动就是补集。这里有个直觉上的陷阱：你找了一个连通区域 A 且它的和等于 target，很容易想当然认为补集 B 也连通。实际上这个结论完全不成立。举个反例结构，在一个 5x5 的矩阵里，如果 A 是正中间一列，这 5 个格子显然连通，但补集是左右两个 2x5 的块，它们之间没有任何相邻边，所以 B 不连通。 这种情况下即使 A 的和等于 target，整个分割也是非法的。

1.3 先修知识：为什么不能直接套二维前缀和

如果题目只要求“找一个矩形区域，使它的和等于某个值”，那二维前缀和做完二分或者枚举就结束了，这是一道中等题。但这里的区域不一定是矩形，可以是任意形状的连通块，比如一个 L 形、一个 T 形、一条蛇形路径，二维前缀和完全处理不了这种非矩形区域。

这道题的本质变成了“枚举矩阵中所有包含某个点的连通块”，这是一个经典的枚举问题。枚举所有连通块的复杂度理论上是指数级的，因为一个连通块可以由很多种形状，但在实际数据范围下，配合剪枝是能过的。至于补集连通性，那就只能老老实实做一次 BFS 或者 DFS 去验证，没法取巧。

2. 核心算法思路：固定起点枚举连通块

2.1 固定 (0,0) 所在区域，一个映射解决去重

我一开始的想法是把所有合法分割都枚举一遍，也就是先选 A 再选 B，但这样每个合法分割会被正反算两次，A 和 B 交换后又是一个重复答案。后来想到一个关键观察：任意一个合法分割中，左上角格子 (0,0) 一定属于 A 或 B 中的一个。如果它属于 B，那我直接把 A 和 B 的名字互换，新的 A 就包含了 (0,0)。

交换名字之后，两个区域的和仍然是 target，因为 A 和 B 的和本来都是 target，所以这依然是一个合法分割。这就意味着：任何一个合法分割，都可以唯一地表示成“以 (0,0) 所在的那个区域作为 A”的形式。 因此我只需要枚举所有包含 (0,0) 的连通区域 A，检查它的和是否为 target、补集是否连通，就能覆盖所有合法分割，而且每个分割正好被统计一次。

这个映射关系是整道题最重要的剪枝。如果不固定 (0,0)，枚举空间直接翻倍，而且还得额外处理 A/B 互换的重复。固定起点之后，搜索空间直接砍半，并且天然避免了重复计数，所谓“一个映射解决去重”就是这个意思。

2.2 状态设计：visited 数组 + 当前和 + 外边界

在实际写搜索的时候，不能真的拿一个 set 去存当前区域的所有格子坐标，那样做状态拷贝太慢。我习惯用一个 m*n 的 visited 布尔数组标记哪些格子已经在 A 区域里，同时维护一个“外边界”集合 frontier，表示当前 A 区域的所有相邻未访问格子。

这一步想清楚为什么需要 frontier：如果每次扩展都扫描整个矩阵找未访问且与 A 相邻的格子，单次扩展代价是 O(m*n)，搜索节点一多就爆炸。而维护 frontier 之后，每次扩展只需要从 frontier 里选一个格子即可，代价降到 O(frontier 大小)。frontier 的更新逻辑是：把选中的格子从 frontier 中移除，再把该格子周围四个方向上未访问且未在 frontier 中的邻居加进去。

这样设计状态还有一个额外好处：因为每个新格子都是从 frontier 中加入的，所以 A 区域天然是连通的，省去了对 A 做连通性验证的开销。这是一个跟朴素的“逐格二选一”枚举完全不同的思路，效率差别非常大。

2.3 补集连通性检查：最容易漏掉的一步

A 区域天然连通之后，唯一还需要验证的就是补集连通性。每次当当前和 cur 恰好等于 target 时，必须停下来对未访问的格子做一次 BFS，统计连通分量数量是否为 1。这里的实现细节是：找到第一个未访问的格子作为起点，BFS 遍历所有未访问格子，最后看访问数量是否等于未访问格子总数。

有一个常见 bug 是用压缩后的坐标做 BFS，比如把二维坐标转成一维编号后直接判断左右相邻，结果忘记跨行的情况。比如编号 3 和编号 4 在一维坐标上相邻，但如果 n 等于 5，编号 3 在第 0 行第 3 列，编号 4 在第 0 行第 4 列，它们是左右相邻的，没问题；可是如果 n 等于 2，编号 3 是第 1 行第 1 列，编号 4 是第 2 行第 0 列，它们其实是斜对角，不是 4-连通的邻居。所以要么用二维坐标系遍历方向数组，要么在做一维编号时通过divmod(pos, n)还原成二维坐标再判断。我推荐直接还原，保险且直观。

3. 剪枝与实现细节

3.1 剩余和剪枝与递归参数设计

搜索题的灵魂是剪枝，这道题最重要的一条剪枝是“剩余和剪枝”。递归的时候除了维护当前和 cur，还要维护一个 rem，表示所有未访问格子的总和。如果 cur + rem < target，说明就算把剩下所有格子全部加入 A，和也到不了 target，必须立即剪枝返回。

这里有个容易踩的坑：rem 必须是“所有未访问格子”的和，而不是“所有未加入 A 的格子”的和。因为补集里的格子虽然不属于 A，但它们仍然“未访问”，一旦后续扩展路径改变，这些格子也可能加入 A。所以递归函数里 rem 应该等于初始 total 减去当前已选区域和 cur，即 rem = total - cur，这样就不需要额外维护了。

还有一个更激进的剪枝：如果格子值都是非负数，那么 cur 只会单调递增，一旦 cur 等于 target 就可以直接检查补集并返回，不需要继续向深处搜索。因为继续加任何非负格子都会让 cur 超过 target，永远不可能再回到 target。这个剪枝要建立在“格子值非负”这个前提上，题目如果没有明确说，就要谨慎使用。我做到这儿的时候特意看了一眼题目描述，格值非负的设定在这道题里是成立的，所以可以放心加。

3.2 边界扩展法：从“选格子”变成“扩边界”

这个技巧我觉得是整道题最优雅的地方。朴素的枚举方式是对每个格子做“选/不选”的二叉树递归，但这样做会产生大量不连通的集合，然后还要验证每个集合是否连通，白费大量计算。边界扩展法则相反：从 (0,0) 这个种子开始，每一步都从当前边界 frontier 里选一个格子加入 A，这样产生的每一个中间状态天然就是连通的。

但这里又冒出一个新问题：同样的连通块，可能通过不同的加入顺序被枚举多次。比如一个 2x2 的方块区域，可以从左上角开始，先加右上角再加左下角，也可以先加左下角再加右上角，最终都是同一个集合，但走了两条不同的递归路径。如果不去重，搜索节点会爆炸，而且答案会重复计数。

我的处理方法是给格子编上唯一 id（0 到 m*n-1），并且规定：每次扩展时只能选择当前 frontier 中 id 最小的那个格子。 这个规则能保证每个连通块只被生成一次。粗略解释一下：对于任意一个最终集合 S，按照“每次选 frontier 中最小 id”的规则生成，选择序列是确定的，所以 S 只对应一条递归路径。具体实现时，frontier 可以用一个有序结构（比如 sorted list）或者简单点，每次在递归函数里从 frontier 中找最小 id，虽然多一点常数，但正确性优先。

3.3 退化情况：一维矩阵、全零矩阵、负数格值

调试的时候一定要考虑到矩阵的特殊形态。如果 m 等于 1 或者 n 等于 1，问题退化成“一个一维数组切成两个连续区间”，此时不需要搜连通块，直接前缀和扫一遍找断点，复杂度 O(n)。很多搜索代码在二维矩阵上没问题，一遇到一维就出各种越界，所以我建议直接把这个退化情况单独拎出来处理。

全零矩阵则是另一种陷阱。如果所有格子都是 0，那么 total 等于 0，target 也等于 0，任意一个连通区域的和都是 0，此时答案可能非常巨大，甚至需要取模。如果题目没有特殊说明，这种极端情况下搜索会枚举出天文数字个连通块，代码直接超时。常见的处理办法是看题目是否对区域面积有约束，或者是否要求统计方案数并取模。刷题的时候遇到这种边界值，建议先跟题目的样例和范围对照一下，确认是否需要特判。

还有一种情况是格值可能为负数，如果题目允许负值，那么 cur 不是单调递增的，cur 等于 target 之后继续扩展还可能再次等于 target，剪枝逻辑完全不同，上一节说的“命中后返回”就不能用了。所以动手写码之前一定要先确认格值约束，这是所有剪枝策略的前提。

4. 代码实现与复杂度分析

4.1 小规模状态压缩兜底方案（可运行）

如果矩阵的格子总数 m*n 不超过 20，最稳的做法是位掩码枚举，代码简单，正确性最容易保证。我把这个版本写出来，当作一个可以直接跑的兜底方案。

from collections import deque from typing import List class Solution: def waysToPartition(self, grid: List[List[int]]) -> int: m, n = len(grid), len(grid[0]) N = m * n total = sum(grid[i][j] for i in range(m) for j in range(n)) if total % 2: return 0 target = total // 2 val = [grid[i][j] for i in range(m) for j in range(n)] sum_mask = [0] * (1 << N) for mask in range(1, 1 << N): lb = mask & -mask idx = lb.bit_length() - 1 sum_mask[mask] = sum_mask[mask ^ lb] + val[idx] full = (1 << N) - 1 def connected(mask: int) -> bool: if mask == 0: return False start = (mask & -mask).bit_length() - 1 seen = 0 q = deque([start]) seen |= 1 << start while q: pos = q.popleft() i, j = divmod(pos, n) for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)): ni, nj = i + di, j + dj if 0 <= ni < m and 0 <= nj < n: nxt = ni * n + nj if (mask >> nxt) & 1 and not ((seen >> nxt) & 1): seen |= 1 << nxt q.append(nxt) return seen == mask ans = 0 for mask in range(1, full): if not (mask & 1): continue if sum_mask[mask] != target: continue if connected(mask) and connected(full ^ mask): ans += 1 return ans

这个版本的核心逻辑就三步：预处理所有掩码的和、枚举包含编号 0 格子的掩码、分别验证 A 区和补集的连通性。因为固定了 mask 必须包含编号 0 的格子，所以不会把同一分割的正反两版都算进去。复杂度是 O(2^N * N)，N 等于 m*n，当 N 为 20 的时候大约一千万次操作，Python 勉强可以跑；如果 N 到 22 就开始吃力了。

4.2 基于边界扩展的 DFS 搜索版

当格子总数超过位掩码能承受的范围时，就要上搜索剪枝了。边界扩展 DFS 的核心代码骨架如下，我刻意保留了剪枝和去重逻辑，方便参考。

from typing import List class Solution: def waysToPartition(self, grid: List[List[int]]) -> int: m, n = len(grid), len(grid[0]) N = m * n total = sum(grid[i][j] for i in range(m) for j in range(n)) if total % 2: return 0 target = total // 2 val = [grid[i][j] for i in range(m) for j in range(n)] visited = [False] * N ans = 0 dirs = ((1, 0), (-1, 0), (0, 1), (0, -1)) def inb(pos): i, j = divmod(pos, n) return 0 <= i < m and 0 <= j < n def check_complement(): start = -1 for pos in range(N): if not visited[pos]: start = pos break if start == -1: return False q = [start] seen = [False] * N seen[start] = True cnt = 0 while q: pos = q.pop() cnt += 1 i, j = divmod(pos, n) for di, dj in dirs: ni, nj = i + di, j + dj if 0 <= ni < m and 0 <= nj < n: nxt = ni * n + nj if not visited[nxt] and not seen[nxt]: seen[nxt] = True q.append(nxt) return cnt == N - sum(visited) def dfs(cur_sum, visited, frontier): nonlocal ans if cur_sum > target: return if cur_sum + (total - cur_sum) < target: return if cur_sum == target: if check_complement(): ans += 1 return if not frontier: return # 去重规则：选 frontier 中 id 最小的格子 nxt_pos = min(frontier) frontier.remove(nxt_pos) # 分支1：不选 nxt_pos，从剩余 frontier 继续 dfs(cur_sum, visited, set(frontier)) # 分支2：选 nxt_pos visited[nxt_pos] = True new_frontier = set(frontier) i, j = divmod(nxt_pos, n) for di, dj in dirs: ni, nj = i + di, j + dj if 0 <= ni < m and 0 <= nj < n: cand = ni * n + nj if not visited[cand]: new_frontier.add(cand) dfs(cur_sum + val[nxt_pos], visited, new_frontier) visited[nxt_pos] = False visited[0] = True frontier = set() i0, j0 = divmod(0, n) for di, dj in dirs: ni, nj = i0 + di, j0 + dj if 0 <= ni < m and 0 <= nj < n: frontier.add(ni * n + nj) dfs(val[0], visited, frontier) return ans

这个版本的思路是在每一层递归中，从当前边界里挑出编号最小的格子，然后分成两个分支：要么放弃这个格子，要么把它加入 A 区域。放弃之后，这个格子以后也不能再选了，这正好对应了“边界最小 id”的唯一生成顺序规则。这样每个连通块只被枚举一次，避免了重复计数。

运行起来之后你会发现，搜索树依然很庞大，但“剩余和剪枝”配合“命中 target 后立即 return”能够砍掉大量分支。如果题目数据范围较大，还可以进一步优化：把 frontier 从 set 改成有序结构，减少 min 操作的耗时；或者把 visited 数组改成整数掩码，通过位运算判断邻居状态。不过这些都是常数优化，核心思路不变。

4.3 复杂度分析与算法选型建议

两个版本的适用场景非常清晰。位掩码枚举版本的编写效率高，不容易出错，适合 m*n 小于等于 20 的矩阵；边界扩展 DFS 版本理论上能处理更大的矩阵，但复杂度高度依赖数据分布和剪枝效果，最坏情况下依然是指数级。

实际刷题时选哪种，取决于你第一眼看到的约束条件：如果 m 和 n 都很小，比如都是 3 或 4，直接位掩码枚举是最省脑子的；如果 mn 达到 25 以上，可以尝试搜索 + 剪枝；如果 mn 超过 30，那大概率这道题另有数学结论，不是纯粹的搜索题，需要回到题目重新分析。 我自己的习惯是先用位掩码版本把思路验证一遍，确认算法正确，再根据数据范围决定要不要改成搜索版。先保证方向对，再追求性能。

5. 常见问题与调试实录

5.1 TLE：剪枝不彻底和重复枚举

TLE 是刷这类题最常遇到的错误。我自己的搜索版本一开始没有做“固定 (0,0)”的去重，结果一个 4x4 的矩阵跑了半天都出不来。原因很简单：每个合法分割被正反统计了两次，搜索工作量直接翻倍，而且那些本来会在中途被剪掉的分支也多走了一遍。

排查方法很简单：写一个计数器统计递归函数的调用次数，然后在本地用 3x3、4x4 的随机小矩阵跑一遍，对比剪枝前后的调用次数。如果发现调用次数是预期结果的指数倍，优先检查去重逻辑，看看是不是最小 id 规则没生效。还有一个常见问题是 frontier 用 set 之后，每次递归都拷贝整个 set，这个拷贝开销很大。可以尝试用列表加 visited 标记来代替，虽然逻辑稍微绕一点，但性能提升明显。

5.2 WA：补集连通性被忽略

这个坑我踩过一次之后印象特别深。当时我写完第一次版本，用题目给的示例能过，就顺手交了一发，结果直接 WA。查了半天发现，我的代码里只验证了 A 区域的和等于 target，完全没验证补集连通性。为什么示例能过？因为示例恰好补集是连通的，掩盖了问题。

调试这类 WA 的最好方式是自己构造一个“A 连通但补集不连通”的矩阵，比如让 A 占满中间一列，补集分成左右两块，然后观察你的代码是否错误地把它当成合法分割输出了。在本地加上一个辅助断言函数，对所有输出方案手动检查补集连通性，能快速暴露问题。另外，检查补集的 BFS 一定要确保被访问的格子数量等于未访问格子总数，而不是等于某个固定值，否则在边界形状变化时会漏判。

5.3 边界值与特殊矩阵的坑

特殊矩阵主要看三类：总和为奇数、target 为 0、一维退化。总和为奇数的情况最省事，开头判断一下直接返回 0，但有人会把 total 除以 2 用整除，结果 target 判断错误，导致整个搜索方向跑偏。我建议直接先做if total % 2: return 0，不要靠后面的搜索去碰运气。

target 为 0 的情况（比如全零矩阵）比较棘手。如果题目保证格值非负，那么cur == target之后必须停止扩展，否则 cur 会变成正数，永远回不到 0。但如果格值里面有负数，这个剪枝就错了。我在调试时遇到过一个情况：一个看起来非常小的矩阵，因为没处理 target 为 0 的爆炸式枚举，直接卡死。最后在本地把矩阵打印出来逐一检查，才意识到问题出在“命中 target 后继续扩展”这条路径上。

5.4 调试技巧：先用 2x2 和 3x3 验证

我调试这道题时用的最快方法，是构造几个手工小矩阵，把答案手算出来，再跟代码输出对比。比如一个 2x2 的全 1 矩阵，总和是 4，target 是 2，包含左上角格子且和为 2 的连通块有两个，分别是横向的两个格子和纵向的两个格子，所以答案应该是 2。再比如 3x3 全 1 矩阵，总和 9 是奇数，答案应该是 0。这两个用例能快速验证最基础的逻辑。

如果想进一步验证连通性和补集检查，可以用我之前构造过的矩阵：

grid = [ [1, 2, 1], [2, 2, 2], [1, 2, 1] ]

总和是 14，target 是 7。左上角 2x2 方块的和是 1 + 2 + 2 + 2 = 7，补集是右边一列加下面一行，具体为 1 + 2 + 2 + 1 + 1 = 7，而且补集是一条连通的折线。这个用例能验证“A 连通 + 补集连通”的真正合法分割。如果代码在这个用例上输出正确，再换那个“中间一列 A、左右两半 B”的反例结构测一次，很快就能定位问题。

6. 个人体会与刷题扩展

6.1 这类题的通法套路

刷多了矩阵分割类题目之后，我总结出一个套路：先找总和和奇偶性，再固定一个必选点去重，然后用边界扩展法枚举连通块，最后验证补集条件。这个套路不仅适用于这一道题，很多类似问题都能套进去。比如“把一个图分成两个连通分量且满足某种权重约束”的题，核心思路其实一样，只是把矩阵换成了图。

很多人在搜索题里栽跟头，不是因为想不出 DFS，而是因为枚举状态太大、没有合适的剪枝。固定起点这一步是全局性的剪枝，能把搜索空间砍掉指数级的分支。边界扩展法则是从结构上避免了无效状态。这两招结合在一起，搜索题的骨架就立起来了。

6.2 从 I 到 II：判定题变成计数题之后

如果这个系列的第一版只是判断是否存在合法分割，那找到一个答案就可以提前退出；到了 II 要求计数，就必须遍历整个搜索树，所有能提前退出的剪枝都不能用了，去重的正确性也变得更加重要。这也是为什么我特别强调“固定 (0,0)”这个映射：在判定版里，重复枚举可能只是浪费时间；在计数版里，重复枚举会让答案直接翻倍，属于致命错误。

从做题策略上讲，遇到系列题的第二版，一定要先跟第一版对比，看新增的约束是什么。是输出方案总数？是要求最小面积？还是两个区域交换算不算同一种？这些细节直接决定搜完整个树还是可以提前剪枝。每多一个限制，状态设计和剪枝逻辑都可能需要调整。

6.3 最后分享一个调试小技巧

我调试这种带连通性检查的搜索题时，会在本地开一个 debug 模式，把每次递归命中的合法分割以字符画的形式打印出来，A 区域用 # 标记，B 区域用 . 标记，然后肉眼检查。字符画能一眼看出补集到底连不连通，比在脑内模拟快得多。

# # . # # . . . .

像上面这样，A 是左上角的 2x2 方块，补集是右边一列加下面一行，是连通的，所以这是一个合法分割的候选。但如果打印出来是：

# . . # . . # . .

A 是中间一列，补集左右分离，哪怕 A 的和等于 target，也是非法方案。这种可视化检查在调试 WA 时非常高效，强烈建议遇到类似问题的时候用上。这道题本身虽然难，但把“固定起点 + 边界扩展 + 补集验证”这套组合拳打熟之后，以后再遇到矩阵分割、连通区域枚举类的题目，都会觉得坦荡很多。