二叉树的dfs就不在这节汇总了，直接看二叉树那篇文章就可以了。

1、剑指 Offer 12.矩阵中的路径

1.1 题目

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
例如，在下面的 3×4 的矩阵中包含单词 “ABCCED”（单词中的字母已标出）：
image.png
示例 1：

输入：board = [[“A”,”B”,”C”,”E”],[“S”,”F”,”C”,”S”],[“A”,”D”,”E”,”E”]], word = “ABCCED” 输出：true

示例 2：

输入：board = [[“a”,”b”],[“c”,”d”]], word = “abcd” 输出：false

1.2 思路

这道题是深度优先搜索和回溯思想的结合。

  1. 由于不能走已经走过的格子，因此需要维护一个二维数组visited，来记录哪些坐标已经走过了，dfs到上下左右的坐标时，需要判断当前的坐标是否已经走过，走过就不能再走了直接return；
  2. 注意dfs的起点，题中意思是路径的起始点可以是矩阵中的任意点，因此需要遍历这个二维数组，以数组中的任意一个点作为路径的起始点去dfs；

  3. 在dfs里需要注意回溯思想中的“添加”和“回退”。进入dfs后，开始下一轮dfs前，如果当前坐标对应的值可以添加到路径，则需要将当前坐标对应的visited二维数组中的点置为true，当前点的dfs退出前，需要将当前坐标对应的visited二维数组中的点置为false；

    1.3 代码

    1. class Solution {
    2.  private boolean[][] visited;
    3.  public boolean exist(char[][] board, String word) {
    4.      int h = board.length;
    5.      int w = board[0].length;
    6.      visited = new boolean[h][w];
    7.      for (int i = 0; i < h; ++i) {
    8.          for (int j = 0; j < w; ++j) {
    9.              if (dfs(i, j, 0, board, word)) {
    10.                  return true;
    11.              }
    12.          }
    13.      }
    14.      return false;
    15.  }
    17.  private boolean dfs(int i, int j, int index, char[][] board, String word) {
    18.      if (board[i][j] != word.charAt(index)) {
    19.          return false;
    20.      }
    21.      if (index == word.length() - 1) {
    22.          return true;
    23.      }
    25.      visited[i][j] = true;
    26.      int[][] directions = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    27.      for (int[] direction: directions) {
    28.          int ii = i + direction[0];
    29.          int jj = j + direction[1];
    30.          if (isValid(ii, jj, board) && !visited[ii][jj]) {
    31.              if (dfs(ii, jj, index + 1, board, word)) {
    32.                  return true;
    33.              }
    34.          }
    35.      }
    36.      visited[i][j] = false;
    37.      return false;
    38.  }
    40.  private boolean isValid(int i, int j, char[][] board) {
    41.      int h = board.length;
    42.      int w = board[0].length;
    43.      return i >= 0 && i < h && j >= 0 && j < w;
    44.  }
    45. }

    2、200. 岛屿数量

    2.1 题目

    给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外，你可以假设该网格的四条边均被水包围。
    示例 1：

    输入：grid = [ [“1”,”1”,”1”,”1”,”0”], [“1”,”1”,”0”,”1”,”0”], [“1”,”1”,”0”,”0”,”0”], [“0”,”0”,”0”,”0”,”0”] ] 输出：1

示例 2：

输入：grid = [ [“1”,”1”,”0”,”0”,”0”], [“1”,”1”,”0”,”0”,”0”], [“0”,”0”,”1”,”0”,”0”], [“0”,”0”,”0”,”1”,”1”] ] 输出：3

2.2 思路

  1. 整体思路是双重for循环，在内循环中的(i, j)点开始dfs，dfs的目的是搜索图中的点，并将走过的1置为0，代表该点已经搜索过；
  2. dfs：
    1. 如果该点已经搜索过（字符为0），或者超出了边界，直接return，不用往这个方向继续搜索了；
    2. 否则将这个点标记为0，代表已经搜索了，然后朝上、下、左、右四个方向分别搜索。

  3. 注意：

    1. 在内层for循环里，只要grid[i][j] == ‘1’，就将结果值 + 1，后续dfs里即使遇到1也不用加，因为都是连着的，算一块岛屿；

    2. grid[i][j]是与字符’0’比较，而不是0。

      2.3 代码

      1. class Solution {
      2. private boolean[][] visited;
      3. public int numIslands(char[][] grid) {
      4.   int m = grid.length;
      5.   int n = grid[0].length;
      6.   int cnt = 0;
      8.   for (int i = 0; i < m; ++i) {
      9.       for (int j = 0; j < n; ++j) {
      10.           if (grid[i][j] == '1') {
      11.               ++cnt;
      12.               dfs(i, j, grid);
      13.           }
      14.       }
      15.   }
      16.   return cnt;
      17. }
      19. private void dfs(int i, int j, char[][] grid) {
      20.   if (!isValid(i, j, grid) || grid[i][j] == '0') {
      21.       return;
      22.   }
      23.   grid[i][j] = '0';
      24.   int[][] directions = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
      25.   for (int[] direction: directions) {
      26.       int ii = i + direction[0];
      27.       int jj = j + direction[1];
      28.       dfs(ii, jj, grid);
      29.   }
      30. }
      32. private boolean isValid (int i, int j, char[][] grid) {
      33.   return i >= 0 && i < grid.length && j >= 0 && j < grid[0].length;
      34. }
      35. }