m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例 1：
输入：board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "ABCCED" 输出：true
【作者：Krahets】
解题思路：
本问题是典型的回溯问题，需要使用深度优先搜索（DFS）+ 剪枝解决。
深度优先搜索： 即暴力法遍历矩阵中所有字符串可能性。DFS 通过递归，先朝一个方向搜到底，再回溯至上个节点，沿另一个方向搜索，以此类推。
剪枝： 在搜索中，遇到“这条路不可能和目标字符串匹配成功”的情况，例如当前矩阵元素和目标字符不匹配、或此元素已被访问，则应立即返回，从而避免不必要的搜索分支。
算法解析：
递归参数： 当前元素在矩阵 board 中的行列索引 i 和 j ，当前目标字符在 word 中的索引 k 。
终止条件：
返回 false ： (1) 行或列索引越界 或 (2) 当前矩阵元素与目标字符不同 或 (3) 当前矩阵元素已访问过 （ (3) 可合并至 (2) ） 。
返回 true ： k = len(word) - 1 ，即字符串 word 已全部匹配。
递推工作：
标记当前矩阵元素： 将 board[i][j] 修改为 空字符 '' ，代表此元素已访问过，防止之后搜索时重复访问。
搜索下一单元格： 朝当前元素的 上、下、左、右 四个方向开启下层递归，使用 或 连接 （代表只需找到一条可行路径就直接返回，不再做后续 DFS ），并记录结果至 res 。
还原当前矩阵元素： 将 board[i][j] 元素还原至初始值，即 word[k] 。
【归纳】
终止条件 找到 k==n-1 / 找不到 越界/不相等
递归条件 从当前位置上下左右找
走过路径标记+需要恢复现场
【注意】
word是String类型，取word的字符需要word.charAt(i);
board为char[ ][ ]类型，‘0’ 是字符，“0”是字符串
class Solution {char[][] board;String word;public boolean exist(char[][] board, String word) {this.board = board;this.word = word;for (int i = 0; i < board.length; i++)for (int j = 0; j < board[0].length; j++)if (dfs(i, j, 0)) // 逐个元素为word开头 遍历是否是 wordreturn true;return false;}public boolean dfs(int i, int j, int k){if(i>=board.length || i<0|| j>=board[0].length || j<0|| board[i][j] !=word.charAt(k)) return false;if(k ==word.length()-1) return true;board[i][j] = '0'; // 标记遍历过boolean res = dfs(i-1,j,k+1) || dfs(i+1,j,k+1) || dfs(i,j-1,k+1) || dfs(i,j+1,k+1);board[i][j] = word.charAt(k); // 恢复现场return res;} }
【确实经典】