题目描述
思路解析动画文字版
核心一句话:每格拆 4 三角,格内按斜杠连、格间按相邻连,最后数连通块。下面每帧都在套它。
输入 · 2×2 网格：先看清输入。四个格子各有一条斜线:左上和右下是斜杠 /,右上和左下是反斜杠 \。眼睛先想象一下这四条线把图切成了几块,等会用并查集把它精确数出来。
拆三角 · 16 个独立：第一步:把每个格子拆成 4 个三角,围成一个菱形,上是 0、右是 1、下是 2、左是 3,整张图一共 16 个三角。一开始谁也不连谁,连通块数就是 16。接下来一格一格地合并。
进入格子 (0,0) · 斜杠 /：轮到第 (0,0) 个格子,它的四个三角编号是 0、1、2、3。这格写的是 斜杠 /,它把「上和左」连成一块、「右和下」连成另一块。先看它和邻居的连接,再按这条斜线连内部。
合并 2 与 8：三角 2 是当前格的下三角,贴着下方格子的上三角 8,中间没有斜线,必然连通,合并。两块并成一块,连通块数从 16 减到 15。
合并 1 与 7：三角 1 是当前格的右三角,贴着右边格子的左三角 7,中间没有斜线,必然连通,合并。两块并成一块,连通块数从 15 减到 14。
合并 0 与 3：按这条斜线,格内三角 0 和 3 属于同一块,合并。两块并成一块,连通块数从 14 减到 13。
合并 1 与 2：按这条斜线,格内三角 1 和 2 属于同一块,合并。两块并成一块,连通块数从 13 减到 12。
进入格子 (0,1) · 反斜杠 \：轮到第 (0,1) 个格子,它的四个三角编号是 4、5、6、7。这格写的是 反斜杠 \,它把「上和右」连成一块、「下和左」连成另一块。先看它和邻居的连接,再按这条斜线连内部。
合并 6 与 12：三角 6 是当前格的下三角,贴着下方格子的上三角 12,中间没有斜线,必然连通,合并。两块并成一块,连通块数从 12 减到 11。
合并 4 与 5：按这条斜线,格内三角 4 和 5 属于同一块,合并。两块并成一块,连通块数从 11 减到 10。
合并 6 与 7：按这条斜线,格内三角 6 和 7 属于同一块,合并。两块并成一块,连通块数从 10 减到 9。
第一行处理完：上面一行两个格子处理完了,合并了几次之后,连通块数现在是 9。还剩下一行没处理,继续往下走。
进入格子 (1,0) · 反斜杠 \：轮到第 (1,0) 个格子,它的四个三角编号是 8、9、10、11。这格写的是 反斜杠 \,它把「上和右」连成一块、「下和左」连成另一块。先看它和邻居的连接,再按这条斜线连内部。
合并 9 与 15：三角 9 是当前格的右三角,贴着右边格子的左三角 15,中间没有斜线,必然连通,合并。两块并成一块,连通块数从 9 减到 8。
合并 8 与 9：按这条斜线,格内三角 8 和 9 属于同一块,合并。两块并成一块,连通块数从 8 减到 7。
合并 10 与 11：按这条斜线,格内三角 10 和 11 属于同一块,合并。两块并成一块,连通块数从 7 减到 6。
进入格子 (1,1) · 斜杠 /：轮到第 (1,1) 个格子,它的四个三角编号是 12、13、14、15。这格写的是 斜杠 /,它把「上和左」连成一块、「右和下」连成另一块。先看它和邻居的连接,再按这条斜线连内部。
已同块 · 12 与 15：要连三角 12 和 15,可一查它们已经在同一个连通块里了,这一步什么都不做,连通块数保持 6。这正是并查集省事的地方:重复的连接自动被忽略,不会重复计数。
合并 13 与 14：按这条斜线,格内三角 13 和 14 属于同一块,合并。两块并成一块,连通块数从 6 减到 5。
全部合并完成：四个格子全部处理完。屏幕上同色的三角属于同一个区域,数一数一共有 5 种颜色,也就是 5 个连通块。这张图被斜线切成了 5 块,答案就是 5。
回放 · 五个区域：再回看一遍:每一种颜色就是一块独立区域。斜杠和反斜杠在中间交错,把网格切出了 5 块互不相连的区域。最终答案 5。
边界先想清:一格空格是 1,一格斜杠是 2,贴边的单线封不出新块。
两个高频追问:一是 3×3 放大加洪水填充的替代法,二是三角编号自洽即可但要全程对齐。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass Solution: def regionsBySlashes(self, grid: List[str]) -> int: def find(x): if p[x] != x: p[x] = find(p[x]) return p[x] def union(a, b): pa, pb = find(a), find(b) if pa != pb: p[pa] = pb nonlocal size size -= 1 n = len(grid) size = n * n * 4 p = list(range(size)) for i, row in enumerate(grid): for j, v in enumerate(row): k = i * n + j if i < n - 1: union(4 * k + 2, (k + n) * 4) if j < n - 1: union(4 * k + 1, (k + 1) * 4 + 3) if v == '/': union(4 * k, 4 * k + 3) union(4 * k + 1, 4 * k + 2) elif v == '\\': union(4 * k, 4 * k + 1) union(4 * k + 2, 4 * k + 3) else: union(4 * k, 4 * k + 1) union(4 * k + 1, 4 * k + 2) union(4 * k + 2, 4 * k + 3) return size复杂度
- 时间：O(n²·α)，4n² 个三角,常数次合并,带路径压缩的并查集近似线性,α 为反阿克曼函数可视作常数
- 空间：O(n²)，父数组存 4n² 个三角的归属
易错点
面试追问把动画讲成自己的话
追问不用并查集,还能怎么做?
追问三角编号一定要 0上1右2下3左吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
等式方程的可满足性
LeetCode 990 · 中等 · 沿着 图论套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题