hot100 岛屿数量(200)
)
本题采用深度优先搜索（DFS）网格染色剪枝算法（又称“沉岛标记法”或“网格洪泛填充法”）解决二维矩阵连通域计数问题。其核心本质是将全局稀疏陆地节点的检索，转化为从任意未访问陆地出发的四向递归图遍历，利用原地状态修改直接消除重复访问并实现物理剪枝。当前提供的源码实现了在时间复杂度 O(m * n) 和额外空间复杂度 O(m * n) 条件下的连通域全盘扫描，最终走向是精准输出二维网格中独立拓扑连通岛屿的绝对总量。
一、 问题本质与数据模型
对于大小为 m x n 的二维网格矩阵 grid，题目给出了两个核心的拓扑结构约束：
四向连通性定义：只有在水平方向（左右）或竖直方向（上下）相邻的陆地字符 '1' 才能被判定为物理互通，对角线方向不算连通。
边界水域包围：网格的四周物理边缘外隐式设定为完全被水字符 '0' 包围。
如果在网格的双重遍历扫描中，仅仅对遇到的每个 '1' 触发简单的计数器累加，将会导致同一个连续的陆地岛屿被重复计数（例如一个 2 x 2 的全陆地矩阵会被错误计为 4 个岛屿）。
为了破除这种数据重复呈现导致的计数失真，算法引入了“种子触发现场染色模型”。当外层的线性双重循环首次碰撞到未被处理的陆地 '1' 时，认定捕获到了一个新岛屿的火种。算法在将全局计数器ans递增后，立即拉起内层 DFS 染色函数。该函数以当前坐标为圆心，向上下左右四个维度呈树状分叉式深探。在每一个步进到的有效陆地单元格上，直接原地将其字符改写为 '2'（标记为已访问/沉岛）。这种原地物理篡改破坏了原数据的分布，使得后续的外层循环无法再次感知到该陆地节点，从而实现了彻底的边界隔离。
二、 算法演进对比
在解决网格连通分量（岛屿）计数问题时，不同图论算法在时空开销及架构设计上存在以下差异：
| 解法名称 | 时间复杂度 | 空间复杂度 | 核心原理 | 物理瓶颈 / 缺陷 |
| 并查集法 (Union-Find) | O(m * n * alpha(m * n)) | O(m * n) | 将每个坐标视作独立节点，扫描并合并相邻陆地，最终统计根节点数 | 动态合并开销较高，需要额外的父节点数组及秩数组物理内存空间 |
| 广度优先搜索 (BFS) | O(m * n) | O(min(m, n)) | 利用显式队列按层向四周扩散染色，队列大小受限于连通域的最长边界 | 需要维护外部辅助队列结构，若网格规模极大可能造成堆内存剧烈起伏 |
| 深度优先搜索（当前解法） | O(m * n) | O(m * n) | 双重循环检索火种，触发四向深探，通过原地修改物理状态实现无锁剪枝 | 依赖运行时调用栈，在整张网格全为陆地的极端拓扑下，栈深可达 O(m * n) |
三、 核心分支控制逻辑与决策证明
当前源码的控制流完全依赖于外层双重循环核验与内层 DFS 的四向边界防护网，其内部决策分支证明如下：
1. 种子触发分支：if (grid[i][j] == '1')
执行：
ans++并激活dfs(grid, i, j)。物理意义：在线性物理扫描中锁定了一块全新的、完全与已知岛屿孤立的未知陆地。触发岛屿总数的质变累加，并以该点为根节点发动清扫。
2. 原地状态覆写：grid[i][j] = '2';
执行：将当前陆地标志修改为状态码 '2'。
数学证明：通过修改内存中的字符，消除了额外申请布尔型
visited[m][n]矩阵的内存开销。字符 '2' 在后续的分支判定中等同于水域 '0' 的逻辑防护效应，确保该节点彻底退出历史搜索舞台。
3. 方向向量集中控制：int[][] dir = ...
执行：利用常数大小的步进偏移矩阵，通过
for (int[] d : dir)驱动状态演进。数学证明：将繁琐的四段式手工硬编码（分别编写上下左右四组 if 语句）收拢至一处循环模型中，降低了分支预测的逻辑开销。
4. 边界安全核验拦截：if (x >= 0 && x < grid.length && ...)
执行：验证新坐标是否越过网格的物理边界，并核验
grid[x][y] == '1'是否成立。数学证明：双重防护机制。前四项边界判定彻底杜绝了数组下标越界异常（ArrayIndexOutOfBoundsException）；末尾的条件则实现了精准制导，只有真正的、未染色的原生陆地才能获得压栈递归的权限，其余状态直接在当前层级被丢弃。
四、 算法执行状态机步进示例
以输入局部矩阵grid = [ ['1', '0'], ['1', '1'] ]为例（规模 2 x 2 ），全局计数器ans及内层递归调用栈的状态机演进过程如下表所示：
| 步骤 | 当前扫描/访问坐标 (i, j) | 单元格状态数值 | 状态判定与执行分支 | 核心物理剪枝与染色动作 | 全局计数器 ans 与栈状态 |
| 初始 | (0, 0) | '1' | 满足外层扫描命中，触发新岛屿 | ans 递增为 1，拉起内层 DFS(0, 0) 探测 | ans = 1, 栈: [ (0,0) ] |
| 1 | (0, 0) [内] | '1' | 执行原地染色，并测试四向偏移量 | 将 grid[0][0] 强制置为 '2'；向下发现 (1, 0) 为 '1' | ans = 1, 栈: [ (0,0), (1,0) ] |
| 2 | (1, 0) [内] | '1' | 执行原地染色，并测试四向偏移量 | 将 grid[1][0] 强制置为 '2'；向右发现 (1, 1) 为 '1' | ans = 1, 栈: [ (0,0), (1,0), (1,1) ] |
| 3 | (1, 1) [内] | '1' | 执行原地染色，发现四周无有效 '1' | 将 grid[1][1] 强制置为 '2'；四向核验失败，触发回溯 | ans = 1, 栈: 逐渐出栈至空 |
| 4 | (0, 1) | '0' | 外层继续直线扫描，不满足触发条件 | 越过水域单元格，不触发任何内层逻辑 | ans = 1, 栈空 |
| 5 | 其余已被染色的坐标 | '2' | 外层继续直线扫描，因不等于 '1' 遭拦截 | 已被物理标记为 '2'，完美规避二次计数，流程结束 | ans = 1, 扫描完结 |
五、 源码实现
class Solution { public int numIslands(char[][] grid) { // 全局岛屿独立连通域计数器 int ans = 0; // 矩阵双重线性扫描，穷举每一个物理格点 for (int i = 0; i < grid.length; i++) { for (int j = 0; j < grid[0].length; j++) { // 条件控制：若发现原生未处理陆地 '1'，代表发现新连通体边界 if (grid[i][j] == '1') { // 计数器执行自增 ans++; // 激活深度优先搜索染色机，清除当前连通体内的所有陆地状态 dfs(grid, i, j); } } } // 返回最终统计出的不连通岛屿绝对总量 return ans; } // 静态方向矩阵映射：依次代表向右、向下、向左、向上四个物理移动偏移行程 private int[][] dir = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; private void dfs(char[][] grid, int i, int j) { // 核心原位剪枝：将当前坐标强制覆写为 '2'，将其从潜在搜索集合中物理剔除 grid[i][j] = '2'; // 迭代处理四个方向的步进演进 for (int[] d : dir) { int x = i + d[0]; int y = j + d[1]; // 四向安全边界防护网：确保索引不越出矩阵实体，且目标格点必须为待处理陆地 '1' if (x >= 0 && x < grid.length && y >= 0 && y < grid[0].length && grid[x][y] == '1') { // 满足准入条件，向下一层级压栈递归执行染色 dfs(grid, x, y); } } } }六、 复杂度分析
1. 时间复杂度：O(m * n)
分析：算法的外层执行了完整的双重嵌套循环，其基准扫描步数等于网格单元格总数 m * n。对于内层的 DFS 而言，尽管包含了递归调用，但由于每个陆地单元格在被首次触碰时便立即执行了状态变迁（由 '1' 覆写为 '2'），因此任何一个网格格点进入递归体的次数至多为 1 次。在各节点内部，四向偏移核验属于常数阶操作 O(1)。
结论：整个网格搜索路径的原子比较与赋值次数与矩阵总规模呈严格的线性正比关系，时间复杂度收敛于 O(m * n)。
2. 空间复杂度：O(m * n)
分析：算法直接利用了输入矩阵进行原地状态标记，没有申请任何与输入规模成正比的外部物理存储矩阵（空间开销 O(1)）。然而，其空间的动态波动完全受限于递归函数的运行时调用栈。在最坏情况下（整张网格全部为陆地，且图拓扑退化为蜿蜒盘旋的单向蛇形链条），递归调用的栈深度将达到最大极限值，即 m * n。
结论：在最坏网络拓扑下，最大额外系统栈空间复杂度表现为 O(m * n)，在完全不连通的极稀疏矩阵下空间复杂度收敛于常数阶 O(1)。