算法之DFS

DFS

深度优先搜索是在得到一个新节点时立即堆新节点进行遍历。DFS常用来求解这种可达性问题。

在实现DFS时需要考虑以下两个问题：

栈，使用栈来保存当前节点信息，当遍历新节点返回时能够继续遍历当前节点。可以使用递归栈。
标记：需要记录那些节点已经遍历过了。

695. 岛屿的最大面积

给定一个包含了一些 0 和 1 的非空二维数组 grid 。

一个岛屿是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为 0 。)

示例 1:

[[0,0,1,0,0,0,0,1,0,0,0,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,1,1,0,1,0,0,0,0,0,0,0,0],
 [0,1,0,0,1,1,0,0,1,0,1,0,0],
 [0,1,0,0,1,1,0,0,1,1,1,0,0],
 [0,0,0,0,0,0,0,0,0,0,1,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,0,0,0,0,0,0,1,1,0,0,0,0]]

对于上面这个给定矩阵应返回 6。注意答案不应该是 11 ，因为岛屿只能包含水平或垂直的四个方向的 1 。

解法

private int[][] direction={{0,1},{0,-1},{1,0},{-1,0}};
  int m,n;

  public int maxAreaOfIsland(int[][] grid) {
      if(grid.length==0||grid[0].length==0){
          return 0;
      }
      m=grid.length;
      n=grid[0].length;
      int maxArea=0;
      for(int i=0;i<m;i++){
          for(int j=0;j<n;j++){
              maxArea=Math.max(maxArea,dfs(grid,i,j));
          }
      }

      return maxArea;
  }

  private int dfs(int[][] grid,int r,int c){
      if(r<0||r>m||c<0||c>n||grid[r][c]==0){
          return 0;
      }
      int area=1; //（r，c）为陆地
      grid[r][c]=0;//标记为已经遍历
      for (int[] d : direction) {
        area+=dfs(grid, r+d[0], c+d[1]);
      }
      return area;
  }

leetcode原题地址

200. 岛屿的数量

给定一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

示例 1:

leetcode原题地址

解法

private int[][] direction={{0,1},{0,-1},{1,0},{-1,0}};
  int m,n;


  public int numIslands(char[][] grid) {
      if(grid.length==0||grid[0].length==0){
          return 0;
      }
      m=grid.length;
      n=grid[0].length;
      int isLand=0;
      for(int i=0;i<m;i++){
          for (int j=0;j<n;j++){
              if (grid[i][j]!='0'){
                  dfs(grid,i,j);
              }
              isLand++;
          }
      }
      return isLand;
  }


  private void dfs(char[][] grid,int r,int c){
      if(r<0||r>=m||c<0||c>=n||grid[r][c]=='0'){
          return ;
      }
      grid[r][c]='0';//标记为已经遍历
      for (int[] d : direction) {
        dfs(grid, r+d[0], c+d[1]);
      }

  }

朋友圈

班上有 N 名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。

给定一个 N * N 的矩阵 M，表示班级中学生之间的朋友关系。如果M[i][j] = 1，表示已知第 i 个和 j 个学生互为朋友关系，否则为不知道。你必须输出所有学生中的已知的朋友圈总数。

示例 1:

输入: 
[[1,1,0],
 [1,1,0],
 [0,0,1]]
输出: 2 
说明：已知学生0和学生1互为朋友，他们在一个朋友圈。
第2个学生自己在一个朋友圈。所以返回2.

leetcode原题地址

解法

private int n;

public int findCircleNum(int[][] M) {
    n=M.length;
    int cnt=0;
    boolean[] hasVisited=new boolean[n];
    for(int i=0;i<n;i++){
        if(!hasVisited[i]){
            dfs(M,hasVisited,i);
            cnt++;
        }
    }
    return cnt;

}

private void dfs(int[][] arr,boolean[] hasVisited,int i){
    hasVisited[i]=true;
    for(int k=0;k<n;k++){
        if(arr[i][k]==1&&!hasVisited[k]){

            dfs(arr,hasVisited,k);
        }
    }

}

130. 被围绕的区域

给定一个二维的矩阵，包含 ‘X’ 和 ‘O’（字母 O）。

找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。

示例:

X X X X
X O O X
X X O X
X O X X

运行你的函数后，矩阵变为：

X X X X
X X X X
X X X X
X O X X

解释:

被围绕的区间不会存在于边界上，换句话说，任何边界上的 ‘O’ 都不会被填充为 ‘X’。任何不在边界上，或不与边界上的 ‘O’ 相连的 ‘O’ 最终都会被填充为 ‘X’。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

leetcode原题地址

解法

private int m;
    private int n;
    int[][] direction={{0,1},{0,-1},{1,0},{-1,0}};

    public void solve(char[][] board) {
        if (board == null || board.length == 0) {
            return;
        } 
        m = board.length;
        n = board[0].length;
        for (int i = 0; i < m; i++) {
            dfs(board, i, 0);
            dfs(board, i, n - 1);
        }
        for (int i = 0; i < n; i++) {
            dfs(board, 0, i);
            dfs(board, m - 1, i);
        } 
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'T') {
                    board[i][j] = 'O';
                } else if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
            }
        }

    }

    private void dfs(char[][] board, int r, int c) {
        if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] != 'O') {
            return;
        }board[r][c] = 'T';
        for (int[] d : direction) {
            dfs(board, r + d[0], c + d[1]);
        }
    }

417. 太平洋大西洋水流问题

给定一个 m x n 的非负整数矩阵来表示一片大陆上各个单元格的高度。“太平洋”处于大陆的左边界和上边界，而“大西洋”处于大陆的右边界和下边界。

规定水流只能按照上、下、左、右四个方向流动，且只能从高到低或者在同等高度上流动。

请找出那些水流既可以流动到“太平洋”，又能流动到“大西洋”的陆地单元的坐标。

提示：

输出坐标的顺序不重要
m 和 n 都小于150

示例：

给定下面的 5x5 矩阵:

  太平洋 ~   ~   ~   ~   ~ 
       ~  1   2   2   3  (5) *
       ~  3   2   3  (4) (4) *
       ~  2   4  (5)  3   1  *
       ~ (6) (7)  1   4   5  *
       ~ (5)  1   1   2   4  *
          *   *   *   *   * 大西洋

返回:

[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (上图中带括号的单元).

leetcode原题地址

解法

private int m, n;
private int[][] matrix;
private int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

public List<List<Integer>> pacificAtlantic(int[][] matrix) {
    List<List<Integer>> ret = new ArrayList<>();
    if (matrix == null || matrix.length == 0) {
        return ret;
    }
    m = matrix.length;
    n = matrix[0].length;
    this.matrix = matrix;
    boolean[][] canReachP = new boolean[m][n];
    boolean[][] canReachA = new boolean[m][n];
    for (int i = 0; i < m; i++) {
        dfs(i, 0, canReachP);
        dfs(i, n - 1, canReachA);
    }
    for (int i = 0; i < n; i++) {
        dfs(0, i, canReachP);
        dfs(m - 1, i, canReachA);
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (canReachP[i][j] && canReachA[i][j]) {
                ArrayList<Integer> list = new ArrayList<>();
                list.add(i);
                list.add(j);
                ret.add(list);
            }
        }
    }
    return ret;
}
private void dfs(int r, int c, boolean[][] canReach) {
    if (canReach[r][c]) {
        return;
    }
    canReach[r][c] = true;
    for (int[] d : direction) {
        int nextR = d[0] + r;
        int nextC = d[1] + c;
        if (nextR < 0 || nextR >= m || nextC < 0 || nextC >= n
                || matrix[r][c] > matrix[nextR][nextC]) {
            continue;
        }
        dfs(nextR, nextC, canReach);
    }
}