算法：单词搜索

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

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

class Solution {
    // 主方法，接受字符矩阵和目标字符串，返回是否存在目标字符串的布尔值
    public boolean exist(char[][] board, String word) {
        // 获取字符矩阵的行数和列数
        int row = board.length, col = board[0].length;
        // 创建一个与字符矩阵相同大小的二维布尔数组，用于记录每个位置是否被访问过
        boolean[][] visited = new boolean[row][col];
        // 遍历字符矩阵中的每个位置
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                // 调用check方法检查当前位置开始是否存在目标字符串
                boolean flag = check(board, visited, i, j, word, 0);
                // 如果存在目标字符串，则返回true
                if(flag) return true;
            }
        }
        // 如果遍历完整个字符矩阵都没有找到目标字符串，则返回false
        return false;
    }

    // 辅助方法，递归检查从给定位置开始是否存在目标字符串
    public boolean check(char[][] board, boolean[][] visited, int i, int j , String word, int k) {
        // 检查是否越界或者当前位置的字符与目标字符串中对应位置的字符不匹配或者已经访问过
        if(i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != word.charAt(k) || visited[i][j]) {
            return false;
        }
        // 将当前位置标记为已访问
        visited[i][j] = true;
        // 如果当前检查的字符是目标字符串的最后一个字符，则说明找到了目标字符串
        if(k == word.length() - 1) return true;
        // 初始化结果标志为false
        boolean res = false;
        // 定义四个方向的偏移量：右、左、下、上
        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        // 对四个方向进行遍历
        for(int[] dir : directions) {
            // 计算新的位置坐标
            int newi = i + dir[0], newj = j + dir[1];
            // 递归调用check方法，继续向下一个位置搜索
            if(check(board, visited, newi, newj, word, k + 1)) {
                res = true;
                break;
            }
        }
        // 回溯，将当前位置标记为未访问
        visited[i][j] = false;
        // 返回结果标志
        return res; 
    }
}