剑指 Offer.12-矩阵中的路径

class Solution {
    public boolean exist(char[][] board, String word) {
        char[] words = word.toCharArray();
        //由于当前题目需要搜索的空间为图 初始节点可能不是左上的节点 需要对全图进行搜索
        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[0].length; j++) {
                if(dfs(board, words, i, j, 0)) return true;
            }
        }
        return false;
    }
    boolean dfs(char[][] board, char[] word, int i, int j, int k) {
        // 边界判断 合法性判断
        if(i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != word[k]) return false;
        // 当所有字母均在此次深度优先搜索中被找到 返回true
        if(k == word.length - 1) return true;
        // 当走过1个字母时，将其值修改为空格 防止重复搜索
        board[i][j] = '\0';
        // 向4个方向进行深度优先搜索 通过||实现剪枝
        boolean res = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1) || 
                      dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i , j - 1, k + 1);
        // 搜索完成后 重新将值赋值回来 复原现场
        board[i][j] = word[k];、
        // 返回结果
        return res;
    }
}