思路：

dfs + 回溯；使用二维布尔数组记录之前的位置是否已经被访问过，如果已经被访问过的话，则在 dfs 的过程中，直接 return false 即可。也就是说，此路已经不通了；如果当前遍历到的字符不等于 board[i][j] 位置上的字符，那么说明此路也是不通的，因此返回 false；至于递归结束的条件：如果指针 start 能够来到 word 的最后一个字符，那么说明能够在矩阵 board 中找到一条路径，此时返回 true；在遍历到当前 board[i][j] 的时候，首先应将该位置的 visited[i][j] 设置为 true，表明访问过；然后，递归地去 board[i][j] 的上下左右四个方向去找，剩下的路径；在 dfs 的过程当中，如果某条路已经不通了，那么那么需要回溯，也就是将 visited[i][j] 位置的布尔值重新赋值为 fasle；最后，返回 ans 即可。

class Solution {    public boolean exist(char[][] board, String word) {        if(board == null || board.length == 0 || board[0].length == 0){            return false;        }        int m = board.length, n = board[0].length;        char[] chars = word.toCharArray();        boolean[][] visited = new boolean[m][n];        for(int i = 0; i < m; i++){            for(int j = 0; j < n; j++){                if(dfs(board, chars, visited, i, j, 0)){                    return true;                }            }        }        return false;    }    private boolean dfs(char[][] board, char[] chars, boolean[][] visited, int i, int j, int start){        if(i < 0 || i >= board.length || j < 0 || j >= board[0].length || chars[start] != board[i][j] || visited[i][j]){            return false;        }        if(start == chars.length - 1){            return true;        }        visited[i][j] = true;        boolean ans = false;        ans = dfs(board, chars, visited, i + 1, j, start + 1)            || dfs(board, chars, visited, i - 1, j, start + 1)            || dfs(board, chars, visited, i, j + 1, start + 1)            || dfs(board, chars, visited, i, j - 1, start + 1);        visited[i][j] = false;        return ans;    }    }