企业官网建设流程全解析

1. FloodFill算法的本质：从一个像素到一整片区域

1.1 先搞懂什么是洪水填充

很多刷题的朋友第一次见到FloodFill这个词是在图像处理软件里——比如Photoshop的油漆桶工具，你点一个区域，颜色就“蔓延”开来填满整个连通区。这个名字的由来很形象：想象你在一个迷宫里倒水，水会顺着所有能走的路流过去，直到被墙壁挡住。算法做的事情和倒水完全一样：从一个起点出发，沿着相邻关系向四周扩散，把所有满足条件的格子都标记或染色。

放到算法题里，它其实是一类问题的总称：在二维矩阵（或网格）中，从某个起点开始，向上下左右四个方向（有的题是八个方向）做深度优先搜索（DFS）或广度优先搜索（BFS），把连通的、满足条件的格子全部处理一遍。这类问题表面上是“矩阵遍历”，内核却是递归、搜索、回溯这三板斧的组合。

FloodFill之所以重要，是因为它几乎是所有图论搜索题目的最小原型。无论是岛屿类问题、着色类问题、迷宫类问题，还是带约束条件的连通域统计，底层都是同一套搜索框架。我刷了几十道这类题后最大的感受是：把它当作一个“搜索模板”来背熟，远比自己每次从零推导要高效得多。

1.2 核心解题框架：方向数组与边界检查

任何FloodFill题目，骨架都是固定的四件事：

1. 方向数组：定义“相邻”的含义。最常用的是上下左右四方向，用两个数组表示：

int dx[4] = {1, -1, 0, 0}; int dy[4] = {0, 0, 1, -1};

有的题（比如扫雷的点击展开）还需要处理对角线，那就是八方向：

int dx[8] = {1, 1, 1, 0, 0, -1, -1, -1}; int dy[8] = {1, 0, -1, 1, -1, 1, 0, -1};

2. 边界检查：每次准备访问邻居之前，先判断新坐标是否在矩阵范围内。这个判断必须放在访问数组下标之前，否则轻则数组越界，重则段错误。我习惯用一个isValid辅助函数：

bool isValid(int x, int y, int n, int m) { return x >= 0 && x < n && y >= 0 && y < m; }

3. 访问标记：为了防止同一个格子被重复访问，必须用一个visited数组或直接在原矩阵上修改。这里有一个非常经典的坑：标记的时机。我最初写DFS经常在递归返回之后才标记，结果导致死循环，后面单独用一节详细说。

4. 递归/迭代结构：DFS用递归最简洁，BFS用队列最直观。选哪种，取决于题目对“搜索顺序”的要求和递归深度会不会爆栈。

1.3 DFS与BFS的选型思维

我知道很多人一看到FloodFill，心里默认就是DFS，因为代码短、好写。但实际面试和竞赛中，选型是有讲究的：

• DFS（递归）：代码最短，逻辑最贴合“洪水蔓延”的直觉。但缺点是递归栈的深度等于连通区域的面积，如果矩阵很大（比如1000×1000全是同一颜色），递归深度可能达到百万级，直接爆栈。面试时如果题目没有明确说矩阵规模，我一般先写DFS，同时心里清楚它可能栈溢出；如果一看规模就是大矩阵，立刻转BFS。

• BFS（队列）：空间复杂度在极端情况下可能更高（队列里存的是一层的节点），但在网格类题目里通常不会超出O(n×m)。BFS还有一个天然优势：它能天然地处理“多源”场景，比如后面要讲的太平洋大西洋水流问题，多源BFS就比DFS更好理解和实现。

• 关于回溯：FloodFill本身一般不涉及“恢复现场”。回溯的核心是“尝试-撤销-再尝试”，适用于路径搜索、排列组合这类需要穷举所有可能的问题。FloodFill只是无脑向四周扩散，不需要撤销，所以真正的回溯题（比如衣橱整理里的路径约束判断）才会用到回溯技巧。这一点很多人混淆，我后面会在衣橱整理题目里展开讲。

2. 从单点到全局：图像渲染、岛屿数量与最大面积

2.1 图像渲染（LeetCode 733）：最标准的FloodFill模板

题目描述很简单：给你一个二维数组image，起点坐标(sr, sc)和一个新颜色newColor，把起点所在的连通区域（颜色与起点相同的格子）全部改成新颜色。

这道题没什么弯弯绕绕，就是最纯粹的洪水填充。唯一要注意的是边界情况：如果起点颜色本身就等于newColor，直接返回原图，否则会陷入死循环。为什么？因为你在DFS里判断“颜色相等就改色”，改完后又判断“颜色相等”，就会无限递归下去。

void dfs(vector<vector<int>>& image, int x, int y, int oldColor, int newColor, int n, int m) { if (!isValid(x, y, n, m) || image[x][y] != oldColor) return; image[x][y] = newColor; for (int i = 0; i < 4; i++) { dfs(image, x + dx[i], y + dy[i], oldColor, newColor, n, m); } } vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) { int n = image.size(), m = image[0].size(); int oldColor = image[sr][sc]; if (oldColor == color) return image; dfs(image, sr, sc, oldColor, color, n, m); return image; }

这里我直接把image矩阵当作visited数组用，改掉颜色就相当于标记了。很多题都可以这样“原地标记”，省掉一个额外的visited矩阵，空间复杂度从O(n×m)降到O(1)。但有个前提：题目允许修改原数组。如果题目禁止修改，就必须单独开一个visited数组，比如下面岛屿数量这道题，如果直接在原始grid上标记有可能影响后续判断，需要谨慎。

2.2 岛屿数量（LeetCode 200）：从单个点到全图扫描

图像渲染是“给你一个起点”，而岛屿数量是“你需要自己找起点”。思路很直接：遍历整个二维网格，每遇到一个没访问过的'1'，就把它当成一个新岛屿，计数器加一，然后对这个起点做一次FloodFill，把整座岛屿全部标记为已访问，之后就不会再重复计数了。

void dfs(vector<vector<char>>& grid, int x, int y, int n, int m) { if (!isValid(x, y, n, m) || grid[x][y] != '1') return; grid[x][y] = '0'; // 直接在原图上标记 for (int i = 0; i < 4; i++) { dfs(grid, x + dx[i], y + dy[i], n, m); } } int numIslands(vector<vector<char>>& grid) { int n = grid.size(), m = grid[0].size(), count = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (grid[i][j] == '1') { count++; dfs(grid, i, j, n, m); } } } return count; }

我第一次做这道题时有个疑问：为什么把grid[i][j]改成'0'不会影响到其他岛屿的判断？后来想明白了，因为每次FloodFill只处理当前连通的岛屿，把它的所有格子都改成'0'，其他岛屿的'1'不受影响。而且我们遍历到某个格子时，如果它是'0'，说明它要么本来就不是陆地，要么已经被前面的岛屿处理过了，不会重复计数。

这道题还有一个变化：如果题目不允许修改原数组，那就需要一个visited矩阵。代码如下：

int numIslands(vector<vector<char>>& grid) { int n = grid.size(), m = grid[0].size(), count = 0; vector<vector<bool>> visited(n, vector<bool>(m, false)); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (grid[i][j] == '1' && !visited[i][j]) { count++; dfs(grid, visited, i, j, n, m); } } } return count; }

两种写法复杂度相同，时间O(n×m)，空间最坏O(n×m)，但“原地修改”的版本在空间上更优，面试时根据题目的限制条件灵活选。

2.3 岛屿的最大面积（LeetCode 695）：在连通过程中统计状态

这道题和岛屿数量很像，只不过要求的是最大面积。所谓面积，就是一次FloodFill能访问到的格子总数。实现上就是在DFS的每次递归里累加并返回。

int dfs(vector<vector<int>>& grid, int x, int y, int n, int m) { if (!isValid(x, y, n, m) || grid[x][y] == 0) return 0; grid[x][y] = 0; // 标记已访问 int area = 1; for (int i = 0; i < 4; i++) { area += dfs(grid, x + dx[i], y + dy[i], n, m); } return area; } int maxAreaOfIsland(vector<vector<int>>& grid) { int n = grid.size(), m = grid[0].size(), ans = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (grid[i][j] == 1) { ans = max(ans, dfs(grid, i, j, n, m)); } } } return ans; }

这里有一个细节值得注意：area的累加方式。每次递归返回的是“当前格子 + 四个方向的面积”，方向之间用加号连接，天然地把整个岛屿的面积算出来了。如果你不习惯递归返回值，也可以用全局变量或者引用参数来统计：

void dfs(vector<vector<int>>& grid, int x, int y, int n, int m, int& area) { if (!isValid(x, y, n, m) || grid[x][y] == 0) return; grid[x][y] = 0; area++; for (int i = 0; i < 4; i++) { dfs(grid, x + dx[i], y + dy[i], n, m, area); } }

两种方式我都用过，返回值的方式更函数式，引用参数的方式更直观。刷题时怎么顺手怎么来，但面试时建议先想清楚哪种代码更不容易出错。

关于这三个题目，我建议按“模板→批量扫描→统计返回值”的顺序去理解，它们是一个递进关系：图像渲染是单点扩散，岛屿数量是把扩散当作标记工具，最大面积是在扩散中收集信息。递进关系理清了，后面所有变体题都只是在这基础上加条件。

3. 逆向思维与多源扩散：被围绕的区域与太平洋大西洋水流问题

3.1 被围绕的区域（LeetCode 130）：从边界反向遍历

题目要求把矩阵中被'X'完全包围的'O'改成'X'，但边界上的'O'以及和边界'O'相连的'O'都不算被包围，要保持原样。

我第一次做这道题时，正着想的思路是：找到所有'O'的连通块，检查每个连通块是否接触边界。这个思路可以，但实现起来很繁琐，需要判断每个连通块是否包含边界格子，还要处理“先标记后判断”的顺序问题。

后来我学到一个非常漂亮的逆向思路：从边界出发，把能和边界连通的'O'全部标记出来，剩下的'O'自然就是被包围的。这样问题就变成了一个简单的从多个边界点出发的FloodFill。

void dfs(vector<vector<char>>& board, int x, int y, int n, int m) { if (!isValid(x, y, n, m) || board[x][y] != 'O') return; board[x][y] = 'A'; // 标记为“与边界连通” for (int i = 0; i < 4; i++) { dfs(board, x + dx[i], y + dy[i], n, m); } } void solve(vector<vector<char>>& board) { int n = board.size(), m = board[0].size(); // 从四边界的'O'开始，把所有边界连通块标记为'A' for (int i = 0; i < n; i++) { if (board[i][0] == 'O') dfs(board, i, 0, n, m); if (board[i][m-1] == 'O') dfs(board, i, m-1, n, m); } for (int j = 0; j < m; j++) { if (board[0][j] == 'O') dfs(board, 0, j, n, m); if (board[n-1][j] == 'O') dfs(board, n-1, j, n, m); } // 遍历整个矩阵：'A'恢复为'O'，其余'O'改为'X' for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (board[i][j] == 'O') board[i][j] = 'X'; else if (board[i][j] == 'A') board[i][j] = 'O'; } } }

这个逆向思维是算法题里非常经典的技巧：正难则反。当正着判断“被包围”很复杂时，反过来找“没被包围”的，剩下的自然就是答案。我把这类题称为“染色法”：用一个新的标记颜色把不符合条件的部分先“染色”隔离出来，最后再统一处理。

3.2 太平洋大西洋水流问题（LeetCode 417）：多源DFS与结果的交集

这道题是FloodFill系列里综合性较强的题目。题意大致是：一个n×m矩阵表示海拔，左上和右上的边界是太平洋，右下的边界是大西洋（题目定义不同版本略有差异，以LeetCode 417为准：左边界和上边界是太平洋，右边界和下边界是大西洋）。水从高处往低处流（只能流到海拔不高于自己的格子），要求返回所有“既能流到太平洋又能流到大西洋”的格子坐标。

最朴素的想法对每个格子模拟水流，复杂度O((n×m)^2)，在矩阵为200×200时直接超时。正确的做法是用逆向思维：从边界出发，从低处往高处走，不走回头路——即搜索时允许往“海拔不小于当前格子”的邻居扩展。这样：

1. 从太平洋边界出发，标记所有能到达的格子；
2. 从大西洋边界出发，标记所有能到达的格子；
3. 两个标记的交集就是答案。

void dfs(vector<vector<int>>& heights, vector<vector<bool>>& visited, int x, int y, int n, int m) { if (visited[x][y]) return; visited[x][y] = true; for (int i = 0; i < 4; i++) { int nx = x + dx[i], ny = y + dy[i]; if (isValid(nx, ny, n, m) && heights[nx][ny] >= heights[x][y]) { dfs(heights, visited, nx, ny, n, m); } } } vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) { int n = heights.size(), m = heights[0].size(); vector<vector<bool>> pac(n, vector<bool>(m, false)); vector<vector<bool>> atl(n, vector<bool>(m, false)); // 太平洋：左边界和上边界 for (int i = 0; i < n; i++) dfs(heights, pac, i, 0, n, m); for (int j = 0; j < m; j++) dfs(heights, pac, 0, j, n, m); // 大西洋：右边界和下边界 for (int i = 0; i < n; i++) dfs(heights, atl, i, m-1, n, m); for (int j = 0; j < m; j++) dfs(heights, atl, n-1, j, n, m); // 取交集 vector<vector<int>> ans; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (pac[i][j] && atl[i][j]) ans.push_back({i, j}); } } return ans; }

这段代码里的核心变化是搜索条件从“==”变成了“>=”，方向从“往低处流”变成“往高处爬”。物理上虽然反了，但逻辑上完全等价——水从边界能流到的地方，就是边界能逆流回去的地方。

我第一次做的时候，疑惑为什么不需要visited去重之外的其他标记。后来想明白：visited不仅用来防止重复访问，还天然作为一个“可达集合”的结果容器。每个DFS跑完，visited矩阵里为true的格子就是这一侧能到达的所有格子。

这道题如果用BFS也能做，反而更贴近“多源扩散”的形象：先把所有边界点压入队列，然后把它们当作一个整体向外扩展。BFS在多源场景下不需要写多个起点，而是初始化时全部入队，很自然。我在实际写题时，多源DFS更常用，因为代码量更少，而且对递归深度有把握时性能足够。

4. 综合模拟与回溯变体：扫雷游戏与衣橱整理

4.1 扫雷游戏（LeetCode 529）：按点击状态分情况讨论

扫雷游戏是FloodFill里少见的“强模拟”题。题目给一个字符矩阵，'M'表示未挖出的地雷，'E'表示未挖出的空地，'B'表示已挖出的空白格，数字字符'1'-'8'表示周围地雷数。点击一个格子，需要根据规则更新矩阵。

规则：

• 如果点中'M'，直接改成'X'（踩雷），游戏结束。
• 如果点中'E'且其周围（八方向）有地雷，则改成数字，不再递归。
• 如果点中'E'且周围没有地雷，则改成'B'，并递归展开所有未挖出的相邻格子。

这题本质上就是一个带条件的FloodFill：只有“当前格子周围没有地雷”才继续扩散。关键是先数清楚当前格子周围的地雷数量，根据数量决定是变成数字还是继续递归。

void dfs(vector<vector<char>>& board, int x, int y, int n, int m) { if (!isValid(x, y, n, m) || board[x][y] != 'E') return; int cnt = 0; for (int i = 0; i < 8; i++) { int nx = x + dx8[i], ny = y + dy8[i]; if (isValid(nx, ny, n, m) && board[nx][ny] == 'M') cnt++; } if (cnt > 0) { board[x][y] = '0' + cnt; // 周围有雷，标数字，不再扩散 } else { board[x][y] = 'B'; for (int i = 0; i < 8; i++) { dfs(board, x + dx8[i], y + dy8[i], n, m); } } } vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) { int x = click[0], y = click[1]; if (board[x][y] == 'M') { board[x][y] = 'X'; // 踩雷 return board; } int n = board.size(), m = board[0].size(); dfs(board, x, y, n, m); return board; }

这题有几个让我印象深刻的坑：

• 递归条件必须要求 board[x][y] == 'E'。如果不加这个条件，你可能在扩展过程中重复访问已经变成'B'的格子，无限递归。加了之后，扩展时只会处理未挖出的空地。
• 数字格子不再扩散。这是游戏逻辑的核心：周围有地雷的格子只是显示数字，起到“警示”作用，不再展开。如果漏掉这个条件，整个游戏变成了把整个矩阵全翻开的无脑填充。
• 八方向遍历。扫雷的“相邻”是八个方向，这和之前四方向的题不一样，方向数组定义错就直接错了，而且要特别注意不要越界。

这道题整体上是对FloodFill的一次“加了约束”的练习：不是所有满足颜色相等的格子都能扩散，而是要满足“周围地雷数为零”这个额外条件。刷完这道题之后，我对“FloodFill不只是同色扩散”有了更深的体会——它可以是任何满足特定预设条件的连通区域扩散。

4.2 衣橱整理（剑指Offer 13 / LeetCode LCP 类似题）：带约束的连通域搜索

衣橱整理这道题，我最初看到觉得和FloodFill八竿子打不着，因为题目描述不是矩阵而是“若干件衣服”的整理方案。但很多题解把它归类到“搜索与回溯”是因为它本质上是一个DFS在状态空间里的遍历：每件衣服可以被选择放进某一类，不同选择组合成了搜索树，需要回溯来穷举所有分配方案。

不过如果面试官把“衣橱整理”当成一个二维网格问题来问——比如“给定一个衣橱的格子布局，某些格子被占据了，你需要从某个格子出发把所有可整理的衣服格子搜索出来”——那它和FloodFill就完全重合了。我遇到过类似这种变体：矩阵中数字0表示空位，数字1表示有衣物，你需要把连通的、可以移动的衣物区域做标记。这就是一个标准的带约束FloodFill：只对数字为1的格子扩散，而且每走过一个格子要标记，避免重复。

这里的关键不是代码本身，而是你对“搜索空间”的理解。衣橱整理更接近于一个回溯问题：在状态空间里搜索合法整理路径，每做一次选择就递归，选择不合法就回溯换一条路。举个例子，如果你有4件衣服需要按颜色红、蓝、白分类，那么整理方案就是所有可能的颜色分配序列，这是一个指数级的搜索树，必须用回溯：

vector<string> colors = {"红", "蓝", "白"}; vector<string> path; void backtrack(vector<string>& clothes, int idx) { if (idx == clothes.size()) { // 记录一种整理方案 return; } for (string color : colors) { path.push_back(color); // 尝试选择 backtrack(clothes, idx + 1); path.pop_back(); // 撤销选择，回到上一层 } }

我个人在实际刷题中的体会是：很多人把“搜索”和“回溯”混为一谈，其实它们的区别很关键——搜索是遍历整个状态空间，回溯是在搜索过程中“尝试→撤销”的递归技巧。FloodFill本身属于搜索，不需要撤销；而像衣橱整理这种“在多个选择中找方案”的题目，才是回溯的用武之地。遇到一棵多分支的搜索树，脑袋里要有“选了这个之后还能不能选别的”的意识，这就是回溯。

5. 高频坑点与调试心得：如何一次写对FloodFill

5.1 死循环与栈溢出：访问标记的时机

这是FloodFill系列里最严重的坑。很多新手写DFS时习惯这样写：

void dfs(vector<vector<int>>& grid, int x, int y) { // 先处理当前格子 grid[x][y] = 0; for (int i = 0; i < 4; i++) { int nx = x + dx[i], ny = y + dy[i]; if (isValid(nx, ny, n, m) && grid[nx][ny] == 1) { dfs(grid, nx, ny); } } }

这个写法是正确的，因为进入递归之前就标记了当前格子。但如果你换一种写法：

void dfs(vector<vector<int>>& grid, int x, int y) { if (grid[x][y] != 1) return; for (int i = 0; i < 4; i++) { int nx = x + dx[i], ny = y + dy[i]; if (isValid(nx, ny, n, m) && grid[nx][ny] == 1) { grid[nx][ny] = 0; // 标记放在递归调用前 dfs(grid, nx, ny); } } }

如果不先标记就调用dfs，那么回到上一层时，邻居又会被其他方向访问一遍，形成“A访问B、B访问A”的无限递归，直接栈溢出。正确做法是：在进入递归的那一刻就完成标记，不管是进入函数体后立刻标记，还是在调用前标记，二选一但绝不能在返回后标记。

5.2 边界条件：从0到n-1的细节

矩阵题里最常见的崩溃原因就是数组越界。我写isValid函数时习惯把矩阵的行列数作为参数传进去，这样最保险：

bool isValid(int x, int y, int n, int m) { return x >= 0 && x < n && y >= 0 && y < m; }

另外，x对应的是行，y对应的是列，千万别弄混。我第一次写200题时，在二维数组上把行和列搞反了，导致访问grid[y][x]而不是grid[x][y]，结果在特殊矩阵下直接越界。调试了半小时才发现问题，从此我统一用x表示行、y表示列，并在代码注释里标明。

5.3 关于“是否需要回溯”的判断

很多人在做DFS题目时会条件反射地问“要不要恢复现场”，然后在FloodFill题里也尝试恢复，导致代码又长又容易错。

我的经验法则是：

• 如果题目要求的是“从起点出发把所有满足条件的格子都染色/标记”，比如图像渲染、岛屿数量、被围绕的区域，不需要回溯。
• 如果题目要求的是“从起点出发找一条路径，需要尝试不同的方向并回退”，比如迷宫类、状态搜索类，需要回溯。

这里有一个特别容易迷惑的场景：有些题目虽然看起来是“找连通区域”，但要求的是“连通区域是否合法”且搜索顺序会影响结果，这时候就需要回溯。被围绕的区域里，如果不用逆向思路而是正着判断，很容易写出需要回溯的版本；用了逆向思路后，反而完全不需要回溯。所以，数据结构选择得当，很多“需要回溯”的题可以转化为“单纯的FloodFill”。

5.4 我在调试中形成的“三板斧”

刷了大量FloodFill题之后，我总结出了一个调试流程，每次遇到新题都按这个顺序来：

1. 先画图。拿纸笔或白板，画一个小的5×5矩阵，手动模拟一遍题目过程，搞清楚“从哪个点开始”、“向哪些方向扩散”、“什么条件下可以扩散”。
2. 先写边界和主循环。把isValid和主循环（遍历矩阵的for循环）先写出来，确保不越界、能遍历。
3. 再写核心递归。递归逻辑尽量保持最简，只有“不满足条件就return+标记+四方向/八方向递归”这三件事。

如果题目复杂（比如扫雷），我还会把“当前格子周围地雷数量”单独封装成一个函数，方便测试时单独验证。调试的时候先用小数据样例验证，再换随机生成的大矩阵做压力测试，防止递归深度过深。

5.5 从这7道题里提炼出的通用套路

最后把这7道题放在一起看，你会发现它们其实是同一个框架的不同变体：

我刷完这一串题后最强烈的感觉是：核心模板一直没变，变的是“你的搜索目标”和“你需要收集的信息”。图像渲染要的是“染色”，岛屿数量要的是“计数”，最大面积要的是“统计”，被围绕的区域要的是“判断包含关系”，水流要的是“多源可达”，扫雷要的是“带条件的展开”，衣橱整理要的是“方案枚举”。一旦你能从“套模板”升级到“看懂题目在问什么、需要收集什么信息”的层面，这些题就不再是背题，而是真正的思路训练。

按照我个人的刷题经验，建议的顺序是：图像渲染→岛屿数量→岛屿最大面积→被围绕的区域→太平洋大西洋水流→扫雷游戏→衣橱整理。前面五道题可以帮你建立FloodFill的手感和逆向思维，扫雷可以练兵分情况讨论，衣橱整理则是在同一个搜索体系下引入回溯概念，为更高难度的DFS题（比如排列组合、N皇后）打好铺垫。这套组合拳打下来，至少对我而言，效果比单刷几十道松散题目要好得多。