算法总结二维网格 (Grid) DFS 遍历通用模板与实战解析在 LeetCode 中二维网格Grid类型的题目非常常见。这类题目通常要求我们寻找路径、连通块或是检测环。本文将结合 LeetCode 1559. 二维网格图中探测环 和 LeetCode 1391. 检查网格中是否存在有效路径 两道经典题目为你总结一套通用的 C DFS 网格遍历模板。一、 核心要素拆解在二维网格中写 DFS无论题目千变万化都离不开以下四大核心组件方向数组 (DIRS)定义当前格子可以向哪些方向移动。访问标记 (vis)记录已经走过的格子防止死循环或重复计算。合法性校验 (Pruning / Validation)判断下一步是否可以走是否越界、是否满足业务逻辑、是否已访问等。DFS 递归主体进入当前状态 - 尝试所有分支 - 校验分支 - 递归进入下一层。二、 通用 DFS 模板结合两道题的精髓尤其是 C14 及 C23 引入的this auto dfs语法非常优雅我们可以提炼出如下通用模板CclassSolution{//1.定义方向数组根据题目可能固定也可能动态 static constexprintDIRS[4][2]{{-1,0},{1,0},{0,-1},{0,1}};//上下左右 public:boolsolveGrid(vectorvectorintgrid){intmgrid.size(),ngrid[0].size();//2.初始化访问数组 vector vis(m,vectorint8_t(n,0));//3.定义 DFS 匿名函数 auto dfs[](this autodfs,intx,inty,/*可能需要的附加状态如 px,py*/)-bool{//[可选]终止条件到达终点等//if(xtargetXytargetY)returntrue;//标记当前节点已访问 vis[x][y]true;//4.扩展下一个状态for(auto[dx,dy]:DIRS/*或者 DIRS[grid[x][y]]等动态方向*/){intixdx,jydy;//5.合法性校验越界检查业务逻辑检查if(0iim0jjn){//【分支 A】如果题目涉及找环且允许访问已访问过的节点只要不是上一步的节点/*if((i!px||j!py)grid[i][j]grid[x][y]){if(vis[i][j]||dfs(i,j,x,y))returntrue;}*///【分支 B】普通的寻路/连通块只访问未访问的节点/*if(!vis[i][j]业务逻辑判断(如管道相连、值相等)){if(dfs(i,j))returntrue;}*/}}returnfalse;};//6.确定搜索起点//场景1固定起点(如从0,0出发)//returndfs(0,0);//场景2全图遍历(如找图中任意位置的环/连通块)//for(inti0;im;i){//for(intj0;jn;j){//if(!vis[i][j]dfs(i,j,-1,-1))returntrue;//}//}returnfalse;}};三、 两道实战题目的差异点总结虽然使用了同一套骨架但两道题在具体细节上展示了网格 DFS 的两种常见变体1. 方向的控制固定方向 vs 状态依赖方向LC 1559 (探测环)方向是全局固定的上下左右 4 个方向。我们在当前格子尝试向四周扩散。LC 1391 (有效路径)方向是由当前格子的状态决定的。管道形状不同能走的方向也不同。因此方向数组变成了DIRS[street_type]这是一个非常重要的状态转移思想。2. 避免走回头路的方式记录父节点 vs 单向管道匹配LC 1559 (探测环)由于是无向图中的环探测最怕的就是A - B - A这种假环。因此 DFS 需要携带(px, py)参数来记录“你是从哪个格子过来的”在遍历时跳过它 (i ! px || j ! py)。LC 1391 (有效路径)只要管道能连通且下一个节点未被访问过 (!vis[i][j])就可以一直走。不需要记录上一步是谁。3. 特殊的连通性校验逻辑LC 1391 (有效路径)独有的难点在于“你能过去不代表对面能接纳你”。因此多了一个contains函数。从(x, y)以(dx, dy)方向走向(i, j)必须保证(i, j)处的管道有一个方向是(-dx, -dy)才能完美对接。4. 搜索起点的选择LC 1559 (探测环)环可能出现在网格的任何一个角落且有多个连通块。因此需要在主函数中使用双重for循环遍历每一个未访问的格子作为起点。LC 1391 (有效路径)明确要求从左上角(0, 0)走到右下角因此属于单源路径搜索直接dfs(0, 0)即可不需要双重循环。四、 结语掌握了这套模板以后遇到二维网格的搜索题目只需按照以下步骤填空确定遍历方向固定还是动态。确定状态记录是否需要vis是否需要记录parent。补全if里的边界和业务规则判定。确定如何触发 DFS。