剑指 Offer 12. 矩阵中的路径（Java）（中等）

剑指 Offer 12. 矩阵中的路径（Java）（中等） 题目描述：

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

例如，在下面的 3×4 的矩阵中包含单词 “ABCCED”（单词中的字母已标出）。

示例 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 <= board.length <= 200
1 <= board[i].length <= 200
board 和 word 仅由大小写英文字母组成

思路：

深搜加回溯。
具体代码解释如下：

class Solution {
    public boolean exist(char[][] board, String word) {
        char[] words = word.toCharArray();
        //建立二维数组，记录该点是否被访问过了。
        boolean[][] visited = new boolean[board.length][board[0].length];
        //一个一个点开始遍历。
        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[0].length; j++) {
                //如果有遍历结果为true的，直接返回结果
                if(dfs(board, words, visited, i, j, 0)) return true;
            }
        }
        return false;
    }
    boolean dfs(char[][] board, char[] word, boolean visited[][], int i, int j, int k) {
        //如果i或j超过边界，返回false。
        //如果被访问过了，返回false。
        //如果当前访问的值不等于预期的字母值，返回false。
        if(i > board.length - 1 || i < 0 || j > board[0].length - 1 || j < 0 || word[k] != board[i][j] || visited[i][j])return false;
        //如果k的长度等于要求字母的长度了，返回true。
        if(k == word.length - 1) return true;
        //标记访问数组，表面该点被访问过了。
        visited[i][j] = true;
        //往四个方向递归，只要有一个返回是真，则结果anw就是真。
        boolean anw = (dfs(board, word, visited, i + 1, j ,k + 1) || dfs(board, word, visited, i, j + 1, k + 1) || 
                       dfs(board, word, visited, i - 1, j, k + 1) || dfs(board, word, visited, i, j - 1, k + 1));
        //回溯，把访问数组重新标记为未访问过，因为接下来的递归可能还会经过该点。
        visited[i][j] = false;
        return anw;
    }
}