当前位置：首页 > news >正文

算法总结：二维网格 (Grid) DFS 遍历通用模板与实战解析

news 2026/7/4 20:18:04

算法总结：二维网格 (Grid) DFS 遍历通用模板与实战解析

在 LeetCode 中，二维网格（Grid）类型的题目非常常见。这类题目通常要求我们寻找路径、连通块或是检测环。本文将结合 LeetCode 1559. 二维网格图中探测环和 LeetCode 1391. 检查网格中是否存在有效路径两道经典题目，为你总结一套通用的 C++ DFS 网格遍历模板。

一、核心要素拆解

在二维网格中写 DFS，无论题目千变万化，都离不开以下四大核心组件：

方向数组 (DIRS)：定义当前格子可以向哪些方向移动。
访问标记 (vis)：记录已经走过的格子，防止死循环或重复计算。
合法性校验 (Pruning / Validation)：判断下一步是否可以走（是否越界、是否满足业务逻辑、是否已访问等）。
DFS 递归主体：进入当前状态 -> 尝试所有分支 -> 校验分支 -> 递归进入下一层。

二、通用 DFS 模板

结合两道题的精髓（尤其是 C++14+ 及 C++23 引入的this auto&& dfs语法，非常优雅），我们可以提炼出如下通用模板：

C++

classSolution{//1.定义方向数组（根据题目可能固定，也可能动态） static constexprintDIRS[4][2]={{-1,0},{1,0},{0,-1},{0,1}};//上下左右 public:boolsolveGrid(vector<vector<int>>&grid){intm=grid.size(),n=grid[0].size();//2.初始化访问数组 vector vis(m,vector<int8_t>(n,0));//3.定义 DFS 匿名函数 auto dfs=[&](this auto&&dfs,intx,inty,/*可能需要的附加状态，如 px,py*/)->bool{//[可选]终止条件：到达终点等//if(x==targetX&&y==targetY)returntrue;//标记当前节点已访问 vis[x][y]=true;//4.扩展下一个状态for(auto&[dx,dy]:DIRS/*或者 DIRS[grid[x][y]]等动态方向*/){inti=x+dx,j=y+dy;//5.合法性校验：越界检查+业务逻辑检查if(0<=i&&i<m&&0<=j&&j<n){//【分支 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(inti=0;i<m;i++){//for(intj=0;j<n;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)即可，不需要双重循环。