📐算法深度优先遍历

发表于 2021/04/20 更新于 2023/10/07

作者 zhangz1w3nCode

2 分钟阅读

1.方法总结💡

1️⃣通过两次for循环 遍历grid二维数组 根据题意进入递归
2️⃣进入递归体后对 边界和遍历过位置return 最后进行上下左右的移动

2.适用题型🎯

1️⃣岛屿类的题目-求岛屿面积、周长、数量

3.注意点❗

1️⃣DFS本质是递归-尤其注意递归结束的条件 if(i<0||i>=row||j<0||j>=col||grid[i][j]!=1) return;
2️⃣注意审题 看进入递归的条件是什么 不要犯经验主义的错误 1进入还是0 进入 1是陆地还是0是 陆地

4.模板🔑

  
class Solution {
    int res;//根据需要记录答案
    int row;//行
    int col;//列
    public int numEnclaves(int[][] grid) {

         row= grid.length;
         col = grid[0].length;

        //特殊处理 例如:边界0/1的情况要处理

        for(int i =0;i<row;i++){
            for(int j=0;j<col;j++){
                if(grid[i][j]==1){ //是陆地就进入
                    res++; //按题目要求统计
                    dfs(i,j,grid);//进行深度遍历
                }
            }
        }

        return res;

    }
     public void dfs(int i,int j,int[][] grid) {
         //越界和重复判断
        if(i<0||i>=row||j<0||j>=col||grid[i][j]!=1) return;

		//遍历过的就设置成别的数
        grid[i][j] = 0;

         //向下遍历
        dfs(i-1,j,grid);
        dfs(i+1,j,grid);
        dfs(i,j+1,grid);
        dfs(i,j-1,grid);
    }
}