问题

DFS主要可以用于解决三种问题

1.可达性/连通性问题

LeetCode上适用题目：
695 查找最大的连通面积
200 矩阵中的连通分量数目
547 好友关系的连通分量数目
130 填充封闭区域
417 能到达的太平洋和大西洋的区域

2.排列问题

LeetCode上适用题目：
17 数字键盘组合
93 IP 地址划分
79 在矩阵中寻找字符串
257 输出二叉树中所有从根到叶子的路径
47 含有相同元素求排列

3.组合问题

LeetCode上适用题目：
77 组合
39 组合求和
40 含有相同元素的求组合求和
216 1-9 数字的组合求和
78 子集
90 含有相同元素求子集
131 分割字符串使得每个部分都是回文数

实现

两个要点：

  • 栈：用栈来保存当前节点信息，当遍历新节点返回时能够继续遍历当前节点。可以使用递归栈。
  • 标记：和 BFS 一样同样需要对已经遍历过的节点进行标记。

695. 岛屿的最大面积

题目描述

给定一个包含了一些 0 和 1的非空二维数组 grid , 一个 岛屿 是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围着。
找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为0。)
示例 1:

  1. [[0,0,1,0,0,0,0,1,0,0,0,0,0],
  2.  [0,0,0,0,0,0,0,1,1,1,0,0,0],
  3.  [0,1,1,0,1,0,0,0,0,0,0,0,0],
  4.  [0,1,0,0,1,1,0,0,1,0,1,0,0],
  5.  [0,1,0,0,1,1,0,0,1,1,1,0,0],
  6.  [0,0,0,0,0,0,0,0,0,0,1,0,0],
  7.  [0,0,0,0,0,0,0,1,1,1,0,0,0],
  8.  [0,0,0,0,0,0,0,1,1,0,0,0,0]]

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

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

对于上面这个给定的矩阵, 返回 0。
注意: 给定的矩阵grid 的长度和宽度都不超过 50。

解题思路

使用 DFS 遍历时返回当前岛屿的面积，便利数组时每次比较当前岛屿面积与最大岛屿面积的大小。

  1. private int m, n;
  2. private int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
  3. public int maxAreaOfIsland (int[][] grid) {
  4.     m = grid.length;
  5.     if (m == 0) return 0;
  6.     n = grid[0].length;
  7.     int maxArea = 0;
  8.     for (int i = 0; i < m; i++) {
  9.         for (int j = 0; j < n; j++) {
  10.             maxArea = Math.max(maxArea, dfs(grid, i, j));
  11.         }
  12.     }
  13.     return maxArea;
  14. }
  15. private int dfs (int[][] grid, int i, int j) {
  16.     if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == 0) {
  17.         return 0;
  18.     }
  19.     grid[i][j] = 0;
  20.     int area = 1;
  21.     for (int[] d : direction) {
  22.         area += dfs(grid, i + d[0], j + d[1]);
  23.     }
  24.     return area;
  25. }

200. 岛屿的个数

题目描述

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

  1. 输入:
  2. 11110
  3. 11010
  4. 11000
  5. 00000
  6. 输出: 1

示例 2:

  1. 输入:
  2. 11000
  3. 11000
  4. 00100
  5. 00011
  6. 输出: 3

解题思路

每次 DFS 完一个岛屿（连通分量）后，计数器+1.

  1. private int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
  2. public int numIslands (char[][] grid) {
  3.     int m = grid.length;
  4.     if (m == 0) return 0;
  5.     int n = grid[0].length;
  6.     int count = 0;
  7.     for (int i = 0; i < m; i++) {
  8.         for (int j = 0; j < n; j++) {
  9.             if (grid[i][j] == '1') {
  10.                 dfs(grid, i, j);
  11.                 count++;
  12.             }
  13.         }
  14.     }
  15.     return count;
  16. }
  17. private void dfs (char[][] grid, int i, int j) {
  18.     if (i >= 0 && j >= 0 && i < grid.length && j < grid[0].length && grid[i][j] == '1') {
  19.         grid[i][j] = '0';
  20.         for (int[] d : direction) {
  21.             dfs(grid, i + d[0], j + d[1]);
  22.         }
  23.     }
  24. }

547. 朋友圈

题目描述

  1. 班上有N名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。给定一个N * N的矩阵M，表示班级中学生之间的朋友关系。如果M[i][j] = 1，表示已知第 i 个和 j 个学生互为朋友关系，否则为不知道。你必须输出所有学生中的已知的朋友圈总数。示例 1:

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

  2. 示例 2:

    1. 输入: 
    2. [[1,1,0],
    3. [1,1,1],
    4. [0,1,1]]
    5. 输出: 1
    6. 说明：已知学生0和学生1互为朋友，学生1和学生2互为朋友，所以学生0和学生2也是朋友，所以他们三个在一个朋友圈，返回1。

  3. 注意：

    1. N 在[1,200]的范围内。
    2. 对于所有学生，有M[i][i] = 1。
    3. 如果有M[i][j] = 1，则有M[j][i] = 1。

解题思路

这一题虽然也是一个二维矩阵，看似与前两个岛屿问题类似，但是本题的矩阵具有对称性，所以for循环被拆成了两部分，一部分遍历每个学生，第二部分对每个学生 DFS。

  1. private int n;
  2. public int findCircleNum (int[][] M) {
  3.     n = M.length;
  4.     boolean[] marked = new boolean[n];
  5.     int circleCount = 0;
  6.     for (int i = 0; i < n; i++) {
  7.         if (!marked[i]) {
  8.             dfs(M, i, marked);
  9.             circleCount++;
  10.         }
  11.     }
  12.     return circleCount;
  13. }
  14. private void dfs (int[][] M, int i, boolean[] marked) {
  15.     marked[i] = true;
  16.     for (int j = 0; j < n; j++) {
  17.         if (M[i][j] == 1 && !marked[j]) {
  18.             dfs(M, j, marked);
  19.         }
  20.     }
  21. }

130. 被围绕的区域

题目描述

给定一个二维的矩阵，包含 'X' 和 'O'（字母 O）。
找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
示例:

  1. X X X X
  2. X O O X
  3. X X O X
  4. X O X X

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

  1. X X X X
  2. X X X X
  3. X X X X
  4. X O X X

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

解题思路

因为所有跟边界上的‘O’连通的区域都不会被包围，所以我们通过 DFS 先找到所有跟边界连通的区域，将这一部分区域标记一下，设为‘T’，跟真正的 ‘O’区分开。
再遍历矩阵，把所有的‘T’还原为‘O’,把所有的‘O’填充为‘X’。

  1. private int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
  2. private int m, n;
  3. public void solve(char[][] board) {
  4.     if (board == null || board.length == 0) {
  5.         return;
  6.     }
  7.     m = board.length;
  8.     n = board[0].length;
  9.     for (int i = 0; i < m; i++) {
  10.         dfs(board, i, 0);
  11.         dfs(board, i, n - 1);
  12.     }
  13.     for (int i = 0; i < n; i++) {
  14.         dfs(board, 0, i);
  15.         dfs(board, m - 1, i);
  16.     }
  17.     for (int i = 0; i < m; i++) {
  18.         for (int j = 0; j < n; j++) {
  19.             if (board[i][j] == 'T') {
  20.                 board[i][j] = 'O';
  21.             } else if (board[i][j] == 'O') {
  22.                 board[i][j] = 'X';
  23.             }
  24.         }
  25.     }
  26. }
  27. private void dfs(char[][] board, int r, int c) {
  28.     if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] != 'O') {
  29.         return;
  30.     }
  31.     board[r][c] = 'T';
  32.     for (int[] d : direction) {
  33.         dfs(board, r + d[0], c + d[1]);
  34.     }
  35. }

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

题目描述

给定一个 m x n 的非负整数矩阵来表示一片大陆上各个单元格的高度。“太平洋”处于大陆的左边界和上边界，而“大西洋”处于大陆的右边界和下边界。
规定水流只能按照上、下、左、右四个方向流动，且只能从高到低或者在同等高度上流动。
请找出那些水流既可以流动到“太平洋”，又能流动到“大西洋”的陆地单元的坐标。
提示：

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

示例：

  1. 给定下面的 5x5 矩阵:
  2.   太平洋 ~   ~   ~   ~   ~ 
  3.        ~  1   2   2   3  (5) *
  4.        ~  3   2   3  (4) (4) *
  5.        ~  2   4  (5)  3   1  *
  6.        ~ (6) (7)  1   4   5  *
  7.        ~ (5)  1   1   2   4  *
  8.           *   *   *   *   * 大西洋
  9. 返回:
  10. [[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (上图中带括号的单元).

解题思路

因为要找到的点需要既能到太平洋（左边界和上边界）又能到大西洋（右边界和下边界），所以我们设置两个boolean[][]矩阵，分别记录一个点是否能到这两个大洋，最后遍历一遍数组，找到既能到太平洋又能到大西洋的坐标点即可。
记录boolean[][]矩阵方法如下：
从高往低找可能不太方便，所以转换思路，以边界为起点，通过 DFS 往高处走，能走到的点说明就是能到大洋的点。
注意：因为在 DFS 中需要用到matrix[][]的内容，所以我们需要定义一个成员变量作为全局变量使用。

  1. private int[][] matrix;
  2. private int m, n;
  3. private int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
  4. public List<int[]> pacificAtlantic (int[][] matrix) {
  5.     List<int[]> ans = new ArrayList<>();
  6.     if (matrix == null || matrix.length == 0) {
  7.         return ans;
  8.     }
  9.     m = matrix.length;
  10.     n = matrix[0].length;
  11.     this.matrix = matrix;
  12.     boolean[][] canReachP = new boolean[m][n];
  13.     boolean[][] canReachA = new boolean[m][n];
  14.     for (int i = 0; i < m; i++) {
  15.         dfs(i, 0, canReachP);
  16.         dfs(i, n - 1, canReachA);
  17.     }
  18.     for (int j = 0; j < n; j++) {
  19.         dfs(0, j, canReachP);
  20.         dfs(m - 1, j, canReachA);
  21.     }
  22.     for (int i = 0; i < m; i++) {
  23.         for (int j = 0; j < n; j++) {
  24.             if (canReachA[i][j] && canReachP[i][j]) {
  25.                 ans.add(new int[]{i, j});
  26.             }
  27.         }
  28.     }
  29.     return ans;
  30. }
  31. private void dfs (int r, int c, boolean[][] canReach) {
  32.     if (canReach[r][c]) {
  33.         return;
  34.     }
  35.     canReach[r][c] = true;
  36.     for (int[] d : direction) {
  37.         int nextRow = r + d[0];
  38.         int nextCol = c + d[1];
  39.         if (nextRow < 0 || nextRow >= m || nextCol < 0 || nextCol >= n
  40.                 || matrix[r][c] > matrix[nextRow][nextCol]) {
  41.             continue;
  42.         }
  43.         dfs(nextRow, nextCol, canReach);
  44.     }
  45. }