DFS深度优先搜索 LeetCode-417

74 阅读 0 评论 49 点赞

我是靠谱客的博主热心香菇，最近开发中收集的这篇文章主要介绍DFS深度优先搜索 LeetCode-417，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

请添加图片描述

这道题需要定义的变量较多，要记录已经遍历过的，能流到太平洋和大西洋的坐标分别记在对应的集合。此外用一个标志位offset，能流到太平洋的offset等于10，能流到大西洋的offset等于100。

上面图只是帮助理解，因为最外面肯定能流到太平洋或者大西洋，所以offset初始值为10或者100，真正的遍历过程并非如此，但是都是从外面的一圈开始遍历，向上下左右满足条件的方向遍历，然后赋予对应的offset值。
解题关键在于DFS函数的编写，根据深度优先搜索的思想，步骤如下：
1、定义一个矩阵matrix，记录陆地表格height每个位置的offset，offset=10表示与太平洋连通，offset=100表示与大西洋连通，从边界开始遍历。
2、定义p_visited集合存放已经遍历过的offset=10的点，用集合a_visited集合存放已经遍历过的offset=100的点。
3、遍历过程中，offset可以累加，当offset=10+100=110时，表示该点既能流向太平洋又能流向大西洋。
4、最后，遍历matrix矩阵，把matrix(i)(j) =110的点返回，则得到想要的路径。
请添加图片描述

class Solution {
    int row;
    int col;
    int[][] dir = {{1,0},{0,1},{-1,0},{0,-1}};
    Set<String> p_v = new HashSet<>();
    Set<String> a_v = new HashSet<>();
    int[][] matrix;
    int[][] heights;
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        row = heights.length;
        col = row == 0 ? 0:heights[0].length;
        matrix = new int[row][col]; 
        this.heights = heights;

        for(int i=0; i<row; i++){
            dfs(i, 0, 10);
            dfs(i, col-1, 100);
        }
        for(int i=0; i<col; i++){
            dfs(0, i, 10);
            dfs(row-1, i, 100);
        }
        List<List<Integer>> res = new ArrayList<>();
        for(int i=0; i<row; i++){
            for(int j=0; j<col; j++){
                if(matrix[i][j] == 110){
                    res.add(List.of(i, j));
                }
            }
        }
        return res;
    }
    private void dfs(int x, int y, int offSet){
    //如果不在大陆范围内，则不作处理
        if(!isInRange(x,y))
            return;
	//判断是否访问过（注意：根据offset的值检查对应的集合该点（x,y）是否已经访问过，如果访问过就不往下执行了）
        String symbol = x+"@"+y;
        if(contain(symbol, offSet))
            return;
	//记录、更新对应位置的offset
        matrix[x][y] += offSet;
        add(symbol, offSet);//然后把该点存放到太平洋或大西洋已访问的集合里，下次不再访问
	//沿着右上左下四个方向继续搜索
        for(int i=0; i<4; i++){
            int newx = x+dir[i][0];
            int newy = y+dir[i][1];
            //条件：坐标移动后依然在大陆范围内，水从高往低流。
            if(isInRange(newx, newy) && heights[newx][newy] >= heights[x][y]){
                String sym = newx+"@"+newy;
                if(contain(sym, offSet))
                    continue;
                dfs(newx, newy, offSet);
            }
        }
    }
    private boolean isInRange(int x, int y){
        return x>=0 && y>=0 && x<row && y<col;
    }
    private boolean contain(String symbol, int offSet){
        if(offSet == 10)
            return p_v.contains(symbol);
        else
            return a_v.contains(symbol);
    }
    private void add(String symbol, int offSet){
        if(offSet == 10)
            p_v.add(symbol);
        else
            a_v.add(symbol);
    }
}